Dijkstra's Shortest Path Algorithm

What is Dijkstra's Shortest Path Algorithm?

Dijkstra's shortest path algorithm finds the shortest path from the source node to the target node.

It is a greedy algorithm which makes it usually more time efficent compared to other dynamic algorithms like the Bellman-Ford Algorithm. However, Dijkstra's algorithm does not work with negative weight.

---

Analysis

Time Complexity
I will only analyze the runtime of Dijkstra's algorithm without the graph building part. I will assume that the graph was given in dictionary form.

If we don't use min-heap:
$O(|V||V|)=O(|V|^2)$
1) We will visit all the nodes, so it should be $O(V)$
2) We will have to go through each nodes in the dist list to get the minimum value node, so that is another $O(V)$

If we use min-heap:
$O(|V|logV)$
1) We will visit all the nodes, so it should be $O(V)$
2) We will be inserting new nodes into the min-heap, which is $O(logV)$.
3) Getting the minimum value node will take $O(1)$ since it will be the root node of the min-heap

Space Complexity
$O(V)$
1) The graph dictionary will consist of V keys.
2) Heap will consist at most V nodes.
3) Set to keep track of nodes visited will take up V space.

---

Evaluation

Advantages
1. Dijkstra's SPA is fast. It is a greedy algorithm, so it can return as soon as the target node has been reach.

Disadvantages
1. Dijkstra's SPA does not work if there is a negative weight in the graph.

---

Implementation

A graph can be implemented in many ways:
1. Adjacency Matrix
2. Adjacency List
3. Dictionary with List Values
I will be choosing to use dictionary with list values, but the implementation itself would not be different in its essence even if the graph was represented in other ways.

Procedure:

1. We will start off from the start node.
2. For the current node,
   1. Add the current node to nodes_visited
   2. Update the distance to current node
   3. For all the neighbors that are not in nodes_to_visit or not in nodes_visited
      1. Calculate the distance to the node. $d[v] = d[u] + w$
      2. Add the node to nodes_to_visit along with the distance to reach it
   4. We will assign the current node as the node with minimum distance from the node. We will choose the root node from the min-heap nodes_to_visit.

We could short circuit the function if we were to end after finding the target node.

---

Code

This code is written based on the Dijkstra's SPA explained in CS 2110: Data Structures class in Cornell.

I've intentionally added unnecessary variables like the frontier_nodes set and probs set in order to explicitly show how Dijkstra's algorithm works. This code was written as a solution for LeetCode Question #1514: Path with Maximum Probability.

More theoretical explanation can be found on Shortest Path Algorithm Lecture on CS 2110 website.

---