Simple Graphs: have no loops and no multiple edges
Depth-first traversal (stack or recursion): visit next neighbor only after traversing all possible edges from the current neighbor and also its neighbors, until the end.
Breadth-first traversal (queue): Visit all neighbors before visiting any of their neighbors (order does not matter).
The shortest (minimal) path has the lowest cost, not the fewest edges. There could be more than one shortest path.
Not only record the shortest distance, but also the path by storing the previous node.
Sudo code:
MST-Prim(G,w,r)
Q = V[G]
foreach u in Q
do: key[u] = ? // initialize to ‘infinity’
key[r] = 0
pi[r] = null
while Q is not empty
do: u = ExtractMin(Q)
// find light edge; u = r first time through
foreach v in Adj[u]
do: if v in Q && w(u,v) < key[v]
// update adjacent nodes
then pi[v] = u
key[v] = w(u,v)
Sudo code:
for each vertex u in G do
for each vertex v in G do
cost[u,v] = c[u,v]
for each vertex w in G do
for each vertex u in G do
for each vertex v in G do
cost[u,v] = min(cost[u,v],
cost[u,w] + cost[w,v]
Reference video: https://www.youtube.com/watch?v=4OQeCuLYj-4
