# Dijkstra’s algorithm

Dijkstra’s algorithm is a Single Source Shortest Path (SSSP) algorithm for graphs with non-negative edge weights. SSSP means that we need to specify a starting node for the algorithm. Once we provide this starting node, Dijkstra’s can tell us the lowest-cost path between the start node and all other nodes in the graph.

It is important to note that, in referring to *shortest paths* in this context, we are referring to the sum of the edge weights along each path — not the number of edges in each path. Thus, in the above diagram, the shortest path from A to H is not A → H (with a cost of 18). Rather, it is A → I → G → H (with a total cost of 6).

## Constraints / Prerequisites:

All edges of the graph need to have a non-negative edge weight.

## Algorithm Summary:

- Maintain a ‘dist’ array where the distance of every node is initialized at positive infinity. Mark the distance to the start node ‘s’ to be 0.
- Maintain a PQ of key-value pairs of (node index, distance) pairs which tell you which node to visit next based on sorted min value.
- Insert (s, 0) into the PQ and loop while PQ is not empty pulling out the next most promising (node index, distance) pair.
- Iterate over all edges outwards from the current node and relax each edge appending a new (node index, distance) key-value pair to the PQ for every relaxation.

## Lazy Implementation:

WIP

## Eager Implementation:

WIP

## Time Complexity:

Depending on the implementation, the runtime is O($E∗log(v)$), fairly competitive vs other shortest path algorithms.