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