最短路径----Dijkstra
程序员文章站
2023-12-22 16:32:46
...
#include <iostream>
using namespace std;
#define MAX 999999
int path[100];
int Choose(int d[],int n,bool s[],int MaxNumber)
{
int i,minpos,min;
min=MaxNumber;minpos=-1;
for(i=0;i<n;i++){
if(d[i]<=min&&!s[i]){
min=d[i];
minpos=i;
}
}
return minpos;
}
void out(int i)
{
if(path[i]==-1){
cout<<"->v"<<i;
}else if(path[i]!=0){
cout<<"->v"<<path[i];
out(path[i]);
}
}
int main()
{
int a,b;
int A[100][100];
while(cin>>a>>b){
int x,y,w,i,j,u,k;
bool s[100];
int d[100];
for(i=0;i<a;i++){
for(j=0;j<a;j++){
if(i==j){
A[i][j]=0;
}else{
A[i][j]=MAX;
}
}
}
for(i=0;i<b;i++){
cin>>x>>y>>w;
A[x][y]=w;
}
for(i=0;i<a;i++){
s[i]=false;
d[i]=A[0][i];
if(i!=0&&d[i]<MAX){
path[i]=0;
}else{
path[i]=-1;
}
}
s[0]=true;d[0]=0;
for(i=1;i<=a-1;i++){
u=Choose(d,a,s,MAX);
s[u]=true;
for(k=0;k<a;k++){
if(!s[k]&&d[u]+A[u][k]<d[k]){
d[k]=d[u]+A[u][k];
path[k]=u;
}
}
}
for(i=1;i<a;i++){
cout<<"v0";
out(i);
if(path[i]==-1){
cout<<" 无最短路径"<<endl;
}else{
cout<<"->v"<<i;
cout<<" "<<d[i]<<endl;;
}
}
}
return 0;
}