Basic Questions — Shortest Paths

Question 1 — BFS shortest distance

Given an unweighted, undirected graph with vertices {A, B, C, D, E, F} and edges {A-B, A-C, B-D, C-D, C-E, D-F, E-F}, what is the shortest distance from A to every other vertex?

Question 2 — Trace Dijkstra

Same graph, but now weighted: A-B=4, A-C=1, B-D=1, C-D=8, C-E=2, D-F=1, E-F=5. Find shortest distances from A.

Question 3 — Why BFS fails on weighted graphs

For the weighted graph in Q2, what answer would naïve BFS give for dist[D], and why is it wrong?

Question 4 — Count Bellman-Ford passes

A directed graph has 5 vertices and 7 edges. Source = vertex 0. After how many passes is Bellman-Ford guaranteed to have finalized all distances (assuming no negative cycle)?

Question 5 — Detecting a negative cycle

A directed graph has edges {(A, B, 1), (B, C, -3), (C, A, 1)}. Is there a negative cycle? How would Bellman-Ford detect it?

Question 6 — Floyd-Warshall loop order

Why is this Floyd-Warshall implementation wrong?

for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]