Home > Backend Development > C++ > Dijkstra shortest path algorithm for C/C++ program

Dijkstra shortest path algorithm for C/C++ program

王林
Release: 2023-08-31 21:05:02
forward
1170 people have browsed it

C / C++程序的Dijkstra最短路径算法

We get a graph with a source vertex. We have to find the shortest path from the source vertex to all other vertices of the graph.

Dijikstra's algorithm is a greedy algorithm for finding the shortest path from a source vertex to the root node of a graph to the root node of the graph.

Algorithm

Step 1 : Create a set shortPath to store vertices that come in the way of the shortest path tree.
Step 2 : Initialize all distance values as INFINITE and assign distance values as 0 for source vertex so that it is picked first.
Step 3 : Loop until all vertices of the graph are in the shortPath.
   Step 3.1 : Take a new vertex that is not visited and is nearest.
   Step 3.2 : Add this vertex to shortPath.
   Step 3.3 : For all adjacent vertices of this vertex update distances. Now check every adjacent vertex of V, if sum of distance of u and weight of edge is elss the update it.
Copy after login

Let us create a program based on this algorithm.

Example

#include <limits.h>
#include <stdio.h>
#define V 9
int minDistance(int dist[], bool sptSet[]) {
   int min = INT_MAX, min_index;
   for (int v = 0; v < V; v++)
   if (sptSet[v] == false && dist[v] <= min)
      min = dist[v], min_index = v;
   return min_index;
}
int printSolution(int dist[], int n) {
   printf("Vertex Distance from Source\n");
   for (int i = 0; i < V; i++)
      printf("%d \t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src) {
   int dist[V];
   bool sptSet[V];
   for (int i = 0; i < V; i++)
      dist[i] = INT_MAX, sptSet[i] = false;
      dist[src] = 0;
   for (int count = 0; count < V - 1; count++) {
      int u = minDistance(dist, sptSet);
      sptSet[u] = true;
      for (int v = 0; v < V; 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];
   }
   printSolution(dist, V);
}
int main() {
   int graph[V][V] = { { 0, 6, 0, 0, 0, 0, 0, 8, 0 },
      { 6, 0, 8, 0, 0, 0, 0, 13, 0 },
      { 0, 8, 0, 7, 0, 6, 0, 0, 2 },
      { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
      { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
      { 0, 0, 6, 14, 10, 0, 2, 0, 0 },
      { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
      { 8, 13, 0, 0, 0, 0, 1, 0, 7 },
      { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
   };
   dijkstra(graph, 0);
   return 0;
}
Copy after login

Output

Vertex Distance from Source
0 0
1 6
2 14
3 21
4 21
5 11
6 9
7 8
8 15
Copy after login

The above is the detailed content of Dijkstra shortest path algorithm for C/C++ program. For more information, please follow other related articles on the PHP Chinese website!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template