for an unweighted graph, a BFS traversal will already provide the shortest path
a shortest path algorithm will find the shortest path between two vertices on a (1) weighted graph with (2) non-negative weights
suppose we want to find the shortest path from $s$ to all other vertices
goal: we want our algorithm to generate two arrays
dist[] — a V-indexed array of cost of shortest path from $s$
pred[] — a V-indexed array of the predecessor in shortest path from $s$
(what is the parent/predecessor of the node, considering the shortest path from $s$)
from these two arrays, we can find the shortest path from $s$ to any vertex in the graph
the process of searching the graph and updating the dist[]
and pred[]
arrays as we traverse
suppose we have
dist[v]
dist[w]
= length of shortest known path from $s$ to $w$
edge($v$, $w$, weight)
dist
suppose we want to find the shortest path from $s$ to all other vertices
dist[]
array to be infinity for all value and pred
to be undefined for all valuesdist
to be 0;curr
= vertex with the lowest dist
that has not been searched yet (for the first iteration, this will be $s$)