What is Dijkstra's Algo
Uniform Cost Search or Dijkstra algo is a search algorithm used to find the shortest path between two points in a graph. It explores the graph by considering the cost of each path from the starting point to other points in the graph.
Imagine you're in a city and you want to reach a specific destination. The city has a network of roads, and each road has a cost associated with it, which represents the distance or time required to travel on that road. The goal is to find the route that has the lowest total cost from your starting point to the destination.
Uniform Cost Search works by exploring the neighboring cities (nodes) starting from your current location. It keeps track of the cost of reaching each city encountered so far. At each step, the algorithm chooses the city with the lowest cumulative cost and expands from there.
The algorithm keeps a priority queue of cities to explore, sorted by their cumulative costs. It visits the city with the lowest cost first and continues expanding until it reaches the destination or exhausts all possible paths. This way, it ensures that the paths with the lowest cumulative costs are explored first.
By considering the costs associated with each road and always choosing the lowest-cost option at each step, Uniform Cost Search guarantees that it will find the path with the minimum total cost between your starting point and the destination.
In summary, Uniform Cost Search is like exploring the city's roads by always taking the cheapest route at each junction, ensuring that you eventually find the most cost-efficient way to reach your destination.
Who invented it?
Uniform Cost Search, also known as Dijkstra's algorithm, was invented by Dutch computer scientist Edsger W. Dijkstra in 1956. Dijkstra originally developed the algorithm to solve the problem of finding the shortest path in a network of cities, which laid the foundation for modern graph theory and network optimization algorithms. His work in this area has had a significant impact on computer science and various applications involving shortest path problems.
Pseudocode
function Dijkstra(Graph, source):
create empty set Q
// Initialization
for each vertex v in Graph:
dist[v] := infinity
prev[v] := undefined
add v to Q
dist[source] := 0
while Q is not empty:
u := vertex in Q with the minimum distance value
remove u from Q
for each neighbor v of u:
alt := dist[u] + distance(u, v)
if alt < dist[v]:
dist[v] := alt
prev[v] := u
return dist[], prev[]
In this pseudocode:
Finally, the algorithm returns two arrays: dist[] containing the shortest distances from the source vertex to each vertex, and prev[] containing the previous vertex on the shortest path from the source to each vertex.
Note that this pseudocode assumes a weighted graph where distance(u, v) gives the cost (weight) of the edge between vertices u and v.
- Graph represents the input graph.
- source is the starting vertex from which the shortest paths are calculated.
- dist[v] represents the current shortest distance from the source to vertex v.
- prev[v] stores the previous vertex on the shortest path from the source to v.
- Q is a set that keeps track of the unvisited vertices.
Finally, the algorithm returns two arrays: dist[] containing the shortest distances from the source vertex to each vertex, and prev[] containing the previous vertex on the shortest path from the source to each vertex.
Note that this pseudocode assumes a weighted graph where distance(u, v) gives the cost (weight) of the edge between vertices u and v.
Sample Code
// C++ code snippet
typedef pair pii;
// Function to perform Dijkstra's algorithm
void dijkstra(vector < vector < pii>>& graph, int source) {
int n = graph.size();
// Create a priority queue to store vertices and their distances
priority_queue < pii, vector < pii>, greater< pii>> pq;
// Create a vector to store distances from source to all vertices
vector < int> dist(n, numeric_limits::max());
// Set the distance of the source vertex to 0
dist[source] = 0;
// Insert the source vertex into the priority queue
pq.push(make_pair(0, source));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
// Traverse the adjacent vertices of u
for (auto& neighbor : graph[u]) {
int v = neighbor.first;
int weight = neighbor.second;
// Check if a shorter path is found
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
// Print the shortest distances from source to all vertices
cout << "Shortest distances from source " << source << ":\n";
for (int i = 0; i < n; ++i) {
cout << "Vertex " << i << ": " << dist[i] << endl;
}
}
int main() {
int n, m;
cout << "Enter the number of vertices: ";
cin >> n;
cout << "Enter the number of edges: ";
cin >> m;
// Create an adjacency list representation of the graph
vector < vector < pii >> graph(n);
cout << "Enter the edges and their weights:\n";
for (int i = 0; i < m; ++i) {
int u, v, weight;
cin >> u >> v >> weight;
graph[u].push_back(make_pair(v, weight));
graph[v].push_back(make_pair(u, weight));
}
int source;
cout << "Enter the source vertex: ";
cin >> source;
// Run Dijkstra's algorithm
dijkstra(graph, source);
return 0;
}
# Python code snippet
import heapq
class Graph:
def __init__(self, V):
self.V = V
self.adjList = [[] for _ in range(V)]
def addEdge(self, u, v, weight):
self.adjList[u].append((v, weight))
self.adjList[v].append((u, weight))
def dijkstra(self, source):
dist = [float('inf')] * self.V
dist[source] = 0
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, weight in self.adjList[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
print(f"Shortest distances from source {source}:")
for i in range(self.V):
print(f"Vertex {i}: {dist[i]}")
# Driver code
V = int(input("Enter the number of vertices: "))
graph = Graph(V)
E = int(input("Enter the number of edges: "))
print("Enter the edges and their weights:")
for _ in range(E):
u, v, weight = map(int, input().split())
graph.addEdge(u, v, weight)
source = int(input("Enter the source vertex: "))
graph.dijkstra(source)
import java.util.*;
class Graph {
private int V;
private List> adjList;
class Node {
int vertex, weight;
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
}
Graph(int V) {
this.V = V;
adjList = new ArrayList<>(V);
for (int i = 0; i < V; i++)
adjList.add(new ArrayList<>());
}
void addEdge(int u, int v, int weight) {
adjList.get(u).add(new Node(v, weight));
adjList.get(v).add(new Node(u, weight));
}
void dijkstra(int source) {
PriorityQueue pq = new PriorityQueue<>(V, Comparator.comparingInt(node -> node.weight));
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
pq.offer(new Node(source, 0));
while (!pq.isEmpty()) {
int u = pq.poll().vertex;
for (Node neighbor : adjList.get(u)) {
int v = neighbor.vertex;
int weight = neighbor.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new Node(v, dist[v]));
}
}
}
System.out.println("Shortest distances from source " + source + ":");
for (int i = 0; i < V; i++) {
System.out.println("Vertex " + i + ": " + dist[i]);
}
}
}
public class DijkstraAlgorithm {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of vertices: ");
int V = scanner.nextInt();
Graph graph = new Graph(V);
System.out.print("Enter the number of edges: ");
int E = scanner.nextInt();
System.out.println("Enter the edges and their weights:");
for (int i = 0; i < E; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int weight = scanner.nextInt();
graph.addEdge(u, v, weight);
}
System.out.print("Enter the source vertex: ");
int source = scanner.nextInt();
graph.dijkstra(source);
}
}