Dijkstra最短路径算法的C ++程序？
Dijkstra的算法（或Dijkstra的最短路径优先算法，SPF算法）是一种用于在图形中的节点之间找到最短路径的算法，例如，该图形可表示道路网络。该算法创建了一条从起始顶点（源）到图中所有其他点的最短路径树。
Dijkstra的算法通过构建与源之间的距离最小的一组节点，从单个源节点中找到最短路径树。
该图具有以下内容-
顶点或节点，在算法中以v或u表示。
连接两个节点的加权边：(u,v)表示一条边，而w(u,v)表示其权重。在右图中，每个边缘的权重用灰色表示。
算法步骤
设置除源顶点以外的所有顶点的距离=无穷大，将源距离设置为0。
将源顶点按格式(distance,vertex)推入最小优先级队列，因为最小优先级队列中的比较将根据顶点距离进行。
弹出与优先级队列距离最小的顶点（首先弹出的顶点=源）。
在“当前顶点距离+边缘权重<下一个顶点距离”的情况下，更新已连接顶点到弹出顶点的距离，然后将具有新距离的顶点推入优先级队列。
如果之前访问了弹出的顶点，请继续使用而不使用它。
再次应用相同的算法，直到优先级队列为空。
给定一个图和图中的一个源顶点，找到从源到给定图中所有顶点的最短路径。给定图权重的G[][]矩阵，图中n个顶点（起始节点）不存在。
输入值
G[max][max]={{0,1,0,3,10},
{1,0,5,0,0},
{0,5,0,2,1},
{3,0,2,0,6},
{10,0,1,6,0}}
n=5
u=0输出结果
Distance of node1=1 Path=1<-0 Distance of node2=5 Path=2<-3<-0 Distance of node3=3 Path=3<-0 Distance of node4=6 Path=4<-2<-3<-0
说明
根据邻接矩阵adj[][]创建成本矩阵C[][]。C[i][j]是从顶点i到顶点j的成本。如果顶点i和j之间没有边，则C[i][j]为无穷大。
数组Visited[]初始化为零。
for(i=0;i<n;i++) visited[i]=0;
如果顶点0是源顶点，则Visited[0]被标记为1。
通过存储顶点编号为0的顶点的成本来创建距离矩阵。从源顶点0到0到n-1。
for(i=1;i<n;i++) distance[i]=cost[0][i];
最初，源顶点的距离为0。即distance[0]=0;
for(i=1;i<n;i++) visited[i]=0;
选择一个顶点w，以使distance[w]最小且visited[w]为0。将Visited[w]标记为1。
重新计算剩余顶点到源的最短距离。
仅，在重新计算距离时，应考虑在访问的数组[]中未标记为1的顶点。即对于每个顶点v
if(visited[v]==0) distance[v]=min(distance[v], distance[w]+cost[w][v])
示例
#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}