Algoritma laluan terpendek Dijkstra untuk program C/C++

王林
Lepaskan: 2023-08-31 21:05:02
ke hadapan
1137 orang telah melayarinya

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

Kami mendapat graf dengan bucu sumber dalam graf. Kita perlu mencari laluan terpendek dari bucu sumber ke semua bucu lain graf.

Algoritma Dijikstra ialah algoritma tamak untuk mencari laluan terpendek dari puncak sumber ke nod punca graf ke nod punca graf.

Algoritma

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.
Salin selepas log masuk

Berdasarkan algoritma ini marilah kita mencipta program.

Contoh

#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;
}
Salin selepas log masuk

Output

Vertex Distance from Source
0 0
1 6
2 14
3 21
4 21
5 11
6 9
7 8
8 15
Salin selepas log masuk

Atas ialah kandungan terperinci Algoritma laluan terpendek Dijkstra untuk program C/C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan
Tentang kita Penafian Sitemap
Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!