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

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)

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$)