Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. The algorithm works by iteratively expanding the frontier of the discovered vertices, always choosing the vertex with the shortest known distance from the source.
Let's walk through an example to illustrate Dijkstra's algorithm.
Consider the following weighted, directed graph:
```
2
A ---------- B
|\ /|
| \ / |
| \ / |
| \ / |
| \ / |
| C |
| / \ |
| / \ |
| / \ |
| / \ |
|/ \|
D ---------- E
3
```
The numbers next to the edges represent the weights. We want to find the shortest paths from node A to all other nodes.
Let's initialize the algorithm:
1. Set the distance from the source node A to itself as 0 and infinity for all other nodes.
2. Mark all nodes as unvisited.
3. Set the current node as A.
```
A: 0
B: ∞
C: ∞
D: ∞
E: ∞
Current Node: A
```
Now, we iteratively select the unvisited node with the smallest distance and update the distances of its neighbors.
1. **Iteration 1:**
- Visit A.
- Update the distances of A's neighbors (B, C, D) based on the current distance to A.
```
A: 0
B: 2
C: ∞
D: ∞
E: ∞
Current Node: B
```
2. **Iteration 2:**
- Visit B.
- Update the distances of B's neighbors (A, C, E) based on the current distance to B.
```
A: 0
B: 2
C: 5
D: ∞
E: ∞
Current Node: D
```
3. **Iteration 3:**
- Visit D.
- Update the distances of D's neighbors (A, B, C, E) based on the current distance to D.
```
A: 0
B: 2
C: 5
D: 8
E: 11
Current Node: C
```
4. **Iteration 4:**
- Visit C.
- Update the distances of C's neighbors (A, B, D) based on the current distance to C.
```
A: 0
B: 2
C: 5
D: 8
E: 11
Current Node: E
```
5. **Iteration 5:**
- Visit E.
- Update the distances of E's neighbors (B, D) based on the current distance to E.
```
A: 0
B: 2
C: 5
D: 8
E: 11
Current Node: (None, algorithm terminates)
```
The final result is the shortest path distances from node A to all other nodes:
- A to B: 2
- A to C: 5
- A to D: 8
- A to E: 11
The shortest path tree can be constructed by following the predecessor pointers from the destination back to the source.
C implementation:
#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices in the graph
// Function to find the vertex with the minimum distance value
// from the set of vertices not yet included in the shortest path tree
int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
// Function to print the constructed distance array
void printSolution(int dist[]) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%c %d\n", 'A' + i, dist[i]);
}
// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src) {
int dist[V]; // The output array dist[i] holds the shortest distance from src to i
int sptSet[V]; // sptSet[i] will be true if vertex i is included in the shortest path tree or the shortest distance from src to i is finalized
// Initialize all distances as INFINITE and sptSet[] as false
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = 1;
// Update dist value of the adjacent vertices of the picked vertex
for (int v = 0; v < V; v++) {
// Update dist[v] only if it is not in the sptSet, there is an edge from
// u to v, and the total weight of path from src to v through u is
// smaller than the current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Print the constructed distance array
printSolution(dist);
}
int main() {
int graph[V][V] = {
{0, 2, 0, 3, 0},
{2, 0, 5, 0, 0},
{0, 5, 0, 0, 0},
{3, 0, 0, 0, 11},
{0, 0, 0, 11, 0}
};
dijkstra(graph, 0); // 0 is the source vertex (A)
return 0;
}
0 Comments