正文
算法-图（1）Dijkstra求最短路径
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
数组dist[]，是当前求到的顶点v到顶点j的最短路径长度
数组path[]存放求到的最短路径，如path[4]=2,path[2]=3,path[3]=0，则路径{0，3，2，4}就是0到4的最短路径
数组S[]存放已经求到了最短路径的结点的集合
算法包括两个并行的for循环：
（1）辅助数组的初始化工作，dist[i]=G.getweight(v,i)，时间复杂度为O(n)。
（2）顶点v是第一个求到了最短路径的结点，dist[v]=0，把它加入数组S[]。
（2）进行最短路径求解工作的二重嵌套循环，时间复杂度为O(n^2)。大循环重复n-1次，每次求出一个结点的最短路径长度dist[u]和最短路径path[u]：
进行n次循环，每次从没有加入S[]的顶点中找出最短路径长度dist[i]最小的点，加入集合。
进行n次循环，每次修改和该点相邻接的结点的最短路径长度dist[j]和最短路径path[j]（先判断边是否存在）。
最后总的时间复杂度为O(n^2)。
template <class T,class E>
void ShortestPath(Graph<T,E>& G,T v,E dist[],int path[]){ //求到顶点v的最短路径存储在path[]中，最短距离存储在dist[]中
//G为带权有向图
int n=G.NumberOfVertices();
bool *S=new bool[n]; //数组S存放已经求到了最短路径的结点的集合
int i,j,k;
E w,min;
for (i=; i<n; i++) {
dist[i]=G.getWeight(v,i);
S[i]=false;
if(i!=v && dist[i]<maxValue) path[i]=v;
else path[i]=-;
}
S[v]=true;dist[v]=; //顶点v加入顶点集合
for (i=; i<n-; i++) {
min=maxValue; //每次循环前重置min和u
int u=v;
for (j=; j<n; j++)
if(S[j]==false && dist[j]<min){ //选不在S中具有最短路径的顶点u
u=j;
min=dist[j];
}
S[u]=true;
for(k=; k<n; k++){
w=G.getWeight(u,k);
if(S[k]==false && w<maxValue && dist[u]+w<dist[k]){
dist[k]=dist[u]+w;
path[k]=u;
}
}
}
}// 从path数组读取最短路径的算法
template <class T,class E>
void printShortestPath(Graph<T,E>& G,int v,E dist[],int path[]){
cout<<"从顶点"<<G.getValue(v)<<"到其它顶点的最短路径为："<<endl;
int i,j,k,n=G.NumberOfVerticles();
int *d=new int[n];
for (i=o; i<n; i++)
if(i!=v){
j=i;k=;
while(j!=v){d[k++]=j;j=path[];}
cout<<"顶点"<<G.getValue(i)<<"的最短路径为"<<G.getValue(v);
while(k>){
cout<<G.getValue(d[--k])<<"";
cont<<"最短路径长度为："<<dist[i]<<endl;
}
}
delete []d;
}
