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

edge relaxation

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)

• relaxation will update data for $w$ if a shorter path from $s$ to $w$ is found
• dist

Dijkstra’s algorithm

suppose we want to find the shortest path from $s$ to all other vertices

1. initialise dist[] array to be infinity for all value and pred to be undefined for all values
2. start at $s$ and set its dist to be 0;
3. let variable curr = vertex with the lowest dist that has not been searched yet (for the first iteration, this will be $s$)