# 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);
}
}

## Time and Space Complexity

Time Complexity:

- With a naive implementation using an adjacency matrix, the time complexity of Dijkstra's algorithm is O(V^2), where V is the number of vertices in the graph.

- With a more efficient implementation using a priority queue (such as a binary heap or Fibonacci heap) to extract the minimum distance vertex, the time complexity can be improved to O((V + E) log V), where E is the number of edges in the graph. This is because each vertex and edge is processed once, and the priority queue operations take logarithmic time.

Space Complexity:

- The space complexity of Dijkstra's algorithm is O(V) to store the distances and previous vertices for each vertex in the graph.

- If a priority queue is used, the space complexity becomes O(V) for the priority queue itself.

It's important to note that these complexities assume a dense graph with O(V^2) or O(E) edges. If the graph is sparse, meaning it has significantly fewer edges, the time complexity of Dijkstra's algorithm can be further improved using specialized data structures such as adjacency lists or using alternative algorithms like A* search.

## Advantages

1. Optimal Solution: Dijkstra's algorithm guarantees to find the shortest path from the source vertex to all other vertices in a graph with non-negative edge weights. It provides an optimal solution by considering the costs of paths.

2. Broad Applicability: Dijkstra's algorithm can be applied to a wide range of problems that involve finding the shortest path, such as navigation systems, network routing, and resource allocation.

3. Flexibility: The algorithm can handle graphs with weighted edges, which allows for more realistic representations of distances, travel times, or any other relevant costs associated with the edges.

4. Incremental Progress: Dijkstra's algorithm iteratively explores vertices based on their distances, gradually expanding the search from the source to other parts of the graph. This incremental progress allows for early identification of the shortest path to each vertex.

## Disadvantages

1. Non-Optimal for Negative Edge Weights: Dijkstra's algorithm does not work correctly when negative edge weights are present in the graph. It assumes that adding positive weights to a path will always decrease the total cost. If negative weights exist, the algorithm may enter an infinite loop or produce incorrect results.

2. Inefficiency in Dense Graphs: Dijkstra's algorithm can become inefficient when applied to dense graphs with many edges. The need to explore and update distances for all vertices in each iteration can lead to a high computational cost.

3. Memory Requirements: The algorithm requires additional memory to store distances and previous vertices for each vertex in the graph, which can be a concern for large graphs.

4. No Consideration of Heuristic Information: Dijkstra's algorithm treats all vertices equally in terms of exploration, without considering any heuristic information or estimated distances to the destination. This can result in unnecessary exploration of paths that are far from the destination.

Overall, Dijkstra's algorithm is a powerful and widely used algorithm for finding shortest paths. However, its limitations with negative edge weights and inefficiency in dense graphs have led to the development of alternative algorithms such as Bellman-Ford or A* search that address these drawbacks in specific scenarios.