Dijkstra Algorithm

Creator
Creator
Seonglae ChoSeonglae Cho
Created
Created
2021 Jun 6 11:27
Editor
Edited
Edited
2023 Nov 2 6:56

Processing relaxing infinity to exact delta (shortest path)

Does not valid when graph contains negative weight cycle
notion image

Iteration

  1. Extract-min X from table
  1. Relax all edges leaving X
    1. apply new distances to table
 
 

Complexity

  • Whole iteration is need per vertex
  • Relaxation step needs to be done per edge
notion image
notion image
BFS
when graph is unweighted graph
 
 
 

Proof is complicate with several lemma

 
 
 
 
 
 

Recommendations