我们得到一个图，图中有一个源顶点。我们必须找到从源顶点到图的所有其他顶点的最短路径。
dijikstra 算法是一种贪心算法，用于找到从源顶点到最短路径图的根节点到图的根节点。
算法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.
基于这个算法让我们创建一个程序。
示例#include <limits.h>#include <stdio.h>#define v 9int 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;}
输出vertex distance from source0 01 62 143 214 215 116 97 88 15
以上就是c / c++程序的dijkstra最短路径算法的详细内容。