Maison > développement back-end > C++ > Algorithme de chemin le plus court de Dijkstra pour le programme C/C++

Algorithme de chemin le plus court de Dijkstra pour le programme C/C++

王林
Libérer: 2023-08-31 21:05:02
avant
1156 Les gens l'ont consulté

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

Nous obtenons un graphique avec un sommet source. Nous devons trouver le chemin le plus court depuis le sommet source vers tous les autres sommets du graphe.

L'algorithme de Dijikstra est un algorithme glouton permettant de trouver le chemin le plus court d'un sommet source au nœud racine d'un graphe jusqu'au nœud racine du graphe.

Algorithme

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.
Copier après la connexion

Créons un programme basé sur cet algorithme.

Exemple

#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;
}
Copier après la connexion

Sortie

Vertex Distance from Source
0 0
1 6
2 14
3 21
4 21
5 11
6 9
7 8
8 15
Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal