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
Unsupported language.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