Example of Dijkstras algorithm A”← EXTRACT-MIN(Q: B D 10 0(A Q:A B C D E E S.:{A} c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17.11
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.11 Example of Dijkstra’s algorithm AA BB DD CC EE 10 3 14 79 8 2 2 Q: A BCDE 0 ∞∞∞∞ S: { A } 0 ∞ ∞ ∞ ∞ “A” ← EXTRACT-MIN(Q):
Example of Dijkstra’s algorithm 10 Relax all edges leaving A B D 10 0(A Q:A B C D E E 103 S.:{A} c 2001 by Charles E Leiserson Introduction to Agorithms Day29L17.12
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.12 Example of Dijkstra’s algorithm AA BB DD CC EE 10 3 14 79 8 2 2 Q: A BCDE 0 ∞∞∞∞ S: { A } 0 10 3 ∞ ∞ 10 3−− Relax all edges leaving A:
Example of Dijkstras algorithm 10 “C”← EXTRACT-MIN(Q: B D 10 0(A Q: A B C D E E 103 S.:{A,C} c 2001 by Charles E Leiserson Introduction to Agorithms Day29L17.13
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.13 Example of Dijkstra’s algorithm AA BB DD CC EE 10 3 14 79 8 2 2 Q: A B C D E 0 ∞∞∞∞ S: { A, C } 0 10 3 ∞ ∞ 10 3−− “C” ← EXTRACT-MIN(Q):