# Dijkstra's Algorithm

## 1. Introduction

• Finds the shortest (lowest-cost) path through a graph from the start node to all other nodes.
• This is the fastest, single-start, shortest path algorithm for directed and undirected networks with unbounded, non-negative edge weights.

## 2. Description of the algorithm

1. Set the current distance to 0 for your chosen beginning node and infinite for all other nodes.
3. Set the current node C to the non-visited node with the shortest current distance.
4. For each neighbor N of your current node C, add the current distance of C to the weight of the edge connecting C-N. Set it as the new current distance of N if it is less than the current distance of N.
5. Mark the current node C as visited.
6. If there are non-visited nodes, go to step 2.

## 3. Dijkstra Pseudocode

This pseudocode is referred to the Florian's lecture.

term: `V = vertex, pq = priority queue, St = staring node, Sp = predecessor, C = unvisited vertex, W = weight`

``` for each vertex V: initialize V's visited mark to false create minimum priority queue, pq, for vertices pq.insert( [St: Sp, 0 ]) St = starting node, Sp = predeccessor node while ( !pq.isEmpty() ): [ C: Pred, Distance ] = pq.removeMinPathWeight() if C is unvisited: mark C as Visited, set predecessor to Previous Vertex, and cost to Distance in the graph for each edge with weight W to unvisited successor(US) of C: pq.insert( [ US: C, Distance + W ] ) ```

## 4. The image that depicting the algorithm operates over

This image of a cute kitten is from a Medium post:An Introduction to Dijkstraâ€™s Algorithm: Theory and Python Implementation