4 minutes

# Dijkstra’s Algorithm explained

Before we dive into what is Dijkstra’s Algorithm, Let’s understand the basic concepts.

### Graphs

Important Points about Graph - Graphs are data structures representing “connections” between nodes. - A graph is a non-linear data structure - Types of Graphs - Unidrected graphs - Nodes are connected by bidirectional edges. - Directed graphs - Directed edges i.e they only traverse in one direction.

### Graph Applications

- Maps: A graph can be used to for building transporation systems, where two destinations can be considered as Nodes and roads connecting as Edges. [1]
- Social Media: Users are Nodes and if they are friends they are connected by edges.[2]
- Operating systems: Resource Allocation graphs illustrate the allocation of resources such as CPU time, memory and I/O device, to different process in a system [3]

### Dijkstra Algorithm

Dijkstra’s Algorithm works by visiting nodes in the graph beginning with a starting point. it then checks the closest not-yet-checked Node, adding its node to the set of nodes to be checked. It expands from strting node until it attains the goal. Dijkstra’s Algorith is guaranteed to find shortest path between source node and destination, as long as none of the edges have non-negative cost.

Example -

For the above graph of me and my friends. Let’s assume I want to find the shortest path between Sid and Sruthi. We will keep a list on of unvisited Nodes

The algorith finds shortest path between source node (Sid) and other nodes.

Sid | 0 |
---|---|

Sri | inf |

Ganesh | 3 |

Meg | inf |

Hrithik | inf |

Sruthi | inf |

Rujul | inf |

Sid | 0 |
---|---|

Sri | inf |

Ganesh | 3 |

Meg | inf |

Hrithik | inf |

Sruthi | 4 |

Rujul | inf |

Sid | 0 |
---|---|

Sri | inf |

Ganesh | 3 |

Meg | 2 |

Hrithik | inf |

Sruthi | 4 |

Rujul | inf |

Sid | 0 |
---|---|

Sri | 1 |

Ganesh | 3 |

Meg | inf |

Hrithik | inf |

Sruthi | inf |

Rujul | inf |

Sid | 0 |
---|---|

Sri | 1 |

Ganesh | 3 |

Meg | 2 |

Hrithik | 4 |

Sruthi | inf |

Rujul | inf |

Sid | 0 |
---|---|

Sri | 1 |

Ganesh | 3 |

Meg | 2 |

Hrithik | 4 |

Sruthi | 4 |

Rujul | 6 |

Shortest path between Sid and Sruthi = 4

### Example Code

```
# Importing the math module to use its infinity constant.
import math
# Defining the graph as a dictionary of nodes and their edges with their corresponding weights.
graph = {'sid':{'ganesh':3,'meg':2, 'sri':1},
'ganesh':{'sid':3,'meg':1, 'sruthi':1},
'sruthi':{'ganesh':1, 'meg':7, 'rujul':2},
'meg':{'sid':2,'hrithik':2,'sruthi':7},
'sri':{'sid':1,'hrithik':5},
'hrithik':{'meg':2,'sri':5,'rujul':3},
'rujul':{'sruthi':2, 'hrithik':3}}
# Defining the starting and ending nodes for the shortest path.
source = 'sid'
destination = 'sruthi'
# Initializing all nodes in the graph as unvisited.
unvisited = graph
# Creating an empty dictionary to store the shortest distance from the source to each node.
shortest_distances = {}
# Creating an empty list to store the shortest path from the source to the destination.
route = []
# Creating an empty dictionary to store the previous node in the shortest path for each node.
path_nodes = {}
# Setting the shortest distance for each node to infinity.
for nodes in unvisited:
shortest_distances[nodes] = math.inf
# Setting the shortest distance for the source node to 0.
shortest_distances[source] = 0
# Repeating the following steps while there are still unvisited nodes.
while unvisited:
# Initializing the minimum node as none.
min_node = None
# Iterating through each unvisited node and updating the minimum node to the one with the shortest distance from the source.
for current_node in unvisited:
if min_node is None:
min_node = current_node
elif shortest_distances[min_node] > shortest_distances[current_node]:
min_node = current_node
# Iterating through each node adjacent to the minimum node and updating their shortest distance if a shorter path is found.
for (node, value) in unvisited[min_node].items():
if value + shortest_distances[min_node] < shortest_distances[node]:
shortest_distances[node] = value + shortest_distances[min_node]
path_nodes[node] = min_node
# Removing the minimum node from the unvisited nodes since its shortest distance has been found.
unvisited.pop(min_node)
# Setting the current node to the destination node.
node = destination
# Printing the shortest distance from the source to each node in the graph.
print(shortest_distances)
#output
{'sid': 0, 'ganesh': 3, 'sruthi': 4, 'meg': 2, 'sri': 1, 'hrithik': 4, 'rujul': 6}
```

### Citations

[1] “The Algorithms Behind The Working Of Google Maps | CodeChef,” CodeChef, Aug. 30, 2021. [Online]. Available: https://blog.codechef.com/2021/08/30/the-algorithms-behind-the-working-of-google-maps-dijkstras-and-a-star-algorithm/

[2] S. L. Mike Curtiss, S. Lassen, and M. Curtiss, “Under the Hood: Building out the infrastructure for Graph Search,” Engineering at Meta, Mar. 06, 2013. [Online]. Available: https://engineering.fb.com/2013/03/06/core-data/under-the-hood-building-out-the-infrastructure-for-graph-search/

[3] “Resource Allocation Graph (RAG) | Operating Systems (OS) | Core CS,” Resource Allocation Graph (RAG) | Operating Systems (OS) | Core CS. [Online]. Available: https://workat.tech/core-cs/tutorial/resource-allocation-graph-rag-os-lz5lltbbl8u7