A shortest path algorithm is an algorithm used to find the shortest path between two nodes in a graph. Here the edges connecting the nodes have weights or costs associated with them. The goal of these algorithms is to find a path that minimizes the sum of edge weights along the path.
Some of the most commonly used shortest-path algorithms include the Dijkstra algorithm, the Bellman-Ford algorithm, and the Floyd-Warshall algorithm. These algorithms can be used in various applications. For example, you can find the shortest route for a delivery truck, the shortest path for data between nodes in a network, or the shortest path for a robot to navigate a maze.
Shortest path algorithms can be classified into two main types:
Single-source shortest-path algorithm and all-pairs shortest-path algorithm. A single-source algorithm finds the shortest path from one source node to all other nodes in the diagram. The all-pairs algorithm finds the shortest path between all pairs of nodes in the graph.
What is Dijkstra's algorithm?
Dijkstra’s Algorithm allows us to find the shortest path between any two vertices of a graph.
It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph.
Points to remember
· Dijkstra's Algorithm basically starts at the node that you choose (the source node) and it analyses the graph to find the shortest path between that node and all the other nodes in the graph.
· The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
· Once the algorithm has found the shortest path between the source node and another node, that node is marked as "visited" and added to the path.
· The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.
Also Read: Learn Data Structures and Algorithms
Working of Dijkstra’s Algorithms
Dijkstra's Algorithm basically starts at the node t hat you choose (the source node) and it analyses the graph to find the shortest path between that node and all the other nodes in the graph.
Dijkstra used this property in the opposite direction i.e., we overestimate the distance of each vertex from the starting vertex. Then we visit each node and its neighbours to find the shortest sub-path to those neighbours.
The algorithm uses a greedy approach in the sense that we find the next best solution hoping that the result is the best solution for the whole problem.
Complexity
Time Complexity - O(E Log V) : where E is the number of edges and V is the number of vertices.
Space Complexity - O(V)
Implementation of Dijkstra’s Algorithms
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
using namespace std;
typedef pair<int, int> pii;
vector<vector<pii>> adj_list;
vector<int> dijkstra(int start, int n) {
vector<int> dist(n, numeric_limits<int>::max());
dist[start] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto v : adj_list[u]) {
int alt_dist = dist[u] + v.second;
if (alt_dist < dist[v.first]) {
dist[v.first] = alt_dist;
pq.push(make_pair(alt_dist, v.first));
}
}
}
return dist;
}
int main() {
int n, m;
cin >> n >> m;
adj_list.resize(n);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj_list[u].push_back(make_pair(v, w));
adj_list[v].push_back(make_pair(u, w));
}
int start;
cin >> start;
vector<int> dist = dijkstra(start, n);
for (int i = 0; i < n; i++) {
cout << "Distance from " << start << " to " << i << " is " << dist[i] << endl;
}
return 0;
}Explanation
· Initialize the starting node as the current node.
· For each neighbour of the current node, calculate the distance from the starting node to the neighbour through the current node. Update the minimum distance to the neighbour if the calculated distance is shorter than the current minimum distance.
·Add the current node to the set of visited nodes.
· Select the unvisited node with the smallest minimum distance as the new current node.
· Repeat steps 2-4 until all nodes have been visited, or there are no more unvisited nodes with a finite minimum distance.
· At this point, the array dist contains the shortest distance to each node from the starting node.
Advantages of Dijkstra Algorithm
· Faster performance on dense charts - The Dijkstra algorithm is faster than the Bellman-Ford algorithm for dense graphs with many edges. This is because the Dijkstra algorithm walks the graph more efficiently, while the Bellmanford algorithm looks at all possible paths from the source node to all other nodes.
· No edges with negative weights - The Dijkstra algorithm cannot handle graphs with negative weight edges, but the Bellman-Ford algorithm can. This means that Dijkstra's algorithm is better suited to graphs where all edge weights are non-negative.
· Low memory usage - The Dijkstra algorithm requires less memory than the Bellman-Ford algorithm because it stores only the distances to nodes explored so far. The Bellman-Ford algorithm, on the other hand, stores distances to every node in the graph.
· Simpler implementation - The Dijkstra algorithm is usually easier to implement than the Bellman-Ford algorithm because it is a simpler algorithm with fewer limiting cases to consider.
Disadvantages of Dijkstra Algorithm
· It conducts a blind scan, which takes a lot of processing time.
· It is unable to manage sharp edges. As a result, acyclic graphs are produced, and the ideal shortest path is frequently impossible to find.
Applications of Dijkstra’s Algorithm
· To determine the quickest route
· In applications for social networking
· Within a phone network
· To locate the places on the map
Read, Also - Depth First Search (DFS) With Example
Comentarios