欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短路径----Dijkstra

程序员文章站 2023-12-22 16:32:46
...

最短路径----Dijkstra

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

 

 

 

上一篇:

下一篇: