Dijkstra’s shortest path algorithm
Dijkstra’s algorithm is a popular algorithms for solving many single-source shortest path problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between two vertices on a graph. It was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956.
The algorithm maintains a set of visited vertices and a set of unvisited vertices. It starts at the source vertex and iteratively selects the unvisited vertex with the smallest tentative distance from the source. It then visits the neighbours of this vertex and updates their tentative distances if a shorter path is found. This process continues until the destination vertex is reached, or all reachable vertices have been visited.
Need for Dijkstra’s Algorithm (Purpose and Use-Cases):
- The need for Dijkstra’s algorithm arises in many applications where finding the shortest path between two points is crucial.
For example, It can be used in the routing protocols for computer networks and also used by map systems to find the shortest path between starting point and the Destination (as explained in How does Google Maps work?)
Can Dijkstra’s Algorithm work on both Directed and Undirected graphs?
Yes, Dijkstra’s algorithm can work on both directed graphs and undirected graphs as this algorithm is designed to work on any type of graph as long as it meets the requirements of having non-negative edge weights and being connected.
- In a directed graph, each edge has a direction, indicating the direction of travel between the vertices connected by the edge. In this case, the algorithm follows the direction of the edges when searching for the shortest path.
- In an undirected graph, the edges have no direction, and the algorithm can traverse both forward and backward along the edges when searching for the shortest path.
Algorithm for Dijkstra’s Algorithm:
- Mark the source node with a current distance of 0 and the rest with infinity.
- Set the non-visited node with the smallest current distance as the current node.
- For each neighbour, N of the current node adds the current distance of the adjacent node with the weight of the edge connecting 0->1. If it is smaller than the current distance of Node, set it as the new current distance of N.
- Mark the current node 1 as visited.
- Go to step 2 if there are any nodes are unvisited.
Greedy Algorithm Notes for GATE Exam [2024]Fractional Knapsack ProblemOptimal File Merge PatternsPrim’s Algorithm for Minimum Spanning Tree (MST)
In the dynamic landscape of algorithmic design, Greedy Algorithms stand out as powerful tools for solving optimization problems. Aspirants preparing for the GATE Exam 2024 are poised to encounter a range of questions that test their understanding of Greedy Algorithms. These notes aim to provide a concise and insightful overview, unraveling the principles and applications of Greedy Algorithms that are likely to be scrutinized in the upcoming GATE examination.
Table of Content
- Introduction to Greedy Algorithms:
- Activity Selection Problem:
- Job Sequencing Problem
- Huffman Coding
- Kruskal’s Minimum Spanning Tree Algorithm
- Dijkstra’s shortest path algorithm
- MCQ Questions for Greedy Algorithm