Dijkstra's algorithm is an algorithm which is used to find the shortest path in a graph with weighted edges. In this article, we'll introduce the algorithm, discuss a high level implementation, and show a full code implementation in multiple languages. If you'd like to skip to the code, feel free to jump to the bottom.

### Dijkstra's Algorithm

**Dijkstra's algorithm** is an algorithm which finds the shortest possible path between two vertices in a graph with weighted edges. In this article, we'll use the terms *vertex* and *node* synonomously. In the most common implementation, this algorithm actually finds the shortest paths between a start node and all other nodes. This algorithm is useful in situations such as:

- Find the fastest route between two cities.
- Determine the cheapest way to nagivate from one point to another.
- Determining degrees of seperation between friends in a social network.

Some applications may require functionality on top of Dijkstra's algorithm to fully implement.

### High Level Algorithm

This algorithm is implemented using three main parts:

- A map object
*shortestPaths*which maps nodes to the shortest path's cost from the start node to that node (so far). - A map object
*prevNodes*which maps nodes to its previous node in its shortest path (so far). - A breadth-first search, starting from the start node.

At the beginning, *shortestPaths* will have one entry which maps the start node to 0. This is done for convenience, and does make sense because the weight to travel from the start node to itself is 0, since we're already there. As the breadth first search proceeds, the shortest path for each node will be set initially to the first path which finds it, then will be updated if another node also touches that node, and that path has a lower cost. At the end, the *shortestPaths* object will contain all shortest paths from the start node to each other node, and *prevNodes* will contain all immediate previous nodes for each node in its shortest path. The full algorithm can be described as:

- Create a map
*shortestPaths*and add an entry in*shortestPaths*to map the start node to 0. - Create a map
*prevNodes*. - Create a queue
*nodesQueue*to store nodes which have been discovered but not yet visited. - Create a set
*visitedNodes*to keep track of nodes which have been visited. - Create a variable
*currentNode*and set to the start node. - While the queue is not empty:
- Add
*currentNode*to*visitedNodes*. - Create a variable
*dist*, get the value mapped to*currentNode*in*shortestPaths*, and assign to*dist*. - For each outgoing node of
*currentNode*: - If the child node has not been visited, add to
*nodesQueue*. - Create a variable
*childDist*and assign to it:*dist*+ weight of the edge from*currentNode*to the child node. - Check if
*prevNodes*has the child node. - If it does, and
*dist*is less than the current best path, set*shortestPaths->[child node]*to*dist*and*prevNodes->[child node]*to*currentNode*. - If it does not, set
*shortestPaths->[child node]*to*dist*and*prevNodes->[child node]*to*currentNode*. - Dequeue from
*nodesQueue*and assign to*currentNode*.

Once all nodes have been visited, *shortestPaths* will have all of the shortest paths from the start node to each other node. We can reconstruct the path itself with a loop starting from the end node: create an empty array for the path, add the current node (starting with the end node) to the path, get the previous node of the current node, and set the current node to that node. When we reach the start node, the path is complete (but in reverse order).

### Space and Time Complexity

The time complexity is determined by two variables: the number of nodes in the graph and the number of edges between nodes. Graphs with many nodes but few edges will take less steps than graphs with many nodes and many edges.

Complexity | Notes | |
---|---|---|

Space | `O(n)` | The algorithm uses two maps, each with n entries. |

Time | `O(n + e)` | This uses two variables: n represents the number of nodes, and e represents the number of edges in the graph. |

### Directed Graphs

In our description and implementation below, we are finding the shortest path on an *undirected* graph, which means we can traverse each edge in either direction. Dijkstra's algorithm also works on directed graphs, which allows for connections between nodes to have different weights based on the direction, and allows some nodes to only connect to others in one direction. To support this, we don't need to change Dijkstra's algorithm at all, just the way we represent graph nodes.

### Full Implementation

In the implementation below, we've created two helper classes: *GraphNode* and *ShortestPath*. **GraphNode** encapsulates a vertex with a string value and outgoing connections to other vertices with weights. **ShortestPath** encapsulates a solution: an array of nodes corresponding to the shortest path and the sum of weights over that path.