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); } }