Shortest path algorithms (Dijkstra, Floyd)
Graph theory · Mathematics
Study notes
Q: Graph: S-A=4, S-B=2, B-A=1, A-T=5, B-T=8. Shortest S to T? Dijkstra from S: dist S=0. Visit B (2): relax A → 2+1=3 < 4 ✓. Visit A (3): relax T → 3+5=8. Visit B's T: 2+8=10 > 8. Shortest S→T: S-B-A-T = 2+1+5 = 8. (Greedy via B beats direct-looking paths!)