Dijkstra's Algorithm

Status: #triage
Tags: #programming, #data-structures
Date: 2022-07-05
Type:
Related: Graphs in C++

Notes

For finding the lowest cost path in a weighted graph.

Pasted image 20220712154526.png

D is the distance from the source to the current path.
P is the path from the previous vertex that we've visited

Pasted image 20220712160833.png

Pasted image 20220712162423.png

In class review page

Pasted image 20220713132611.png

Dijkstra's Time Complexity = V Log(V) + E Log(V) where E is edges and V is vertices
OR V+E log(V)

Questions

For homework, write down the path like this
Pasted image 20220713135212.png

Does Dijkstra's work with negative weight?

No, we must use Bellman-Ford

Snippets

Pseudocode
Pasted image 20220713135343.png

Terms

Resources

Dijkstra's Algo Notes
Dijkstra's Algorithm Wiki

Hash Tables
CSS 343 - Data Structures, Algorithms, and Discrete Math II