新建 文本文档.txt

求最短路径的问题

#include <iostream.h>  
#include <fstream.h>  
#define M 99999  
int main()  
{  
int G[100][100];  
int n;  
int p[100],flag[100],s[100];  
int cur;  
int m,k,l,i,j;  
ifstream fin("in.txt");  
//enter  
fin>>n;  
for(i=0;i<n;i++)  
for(j=0;j<n;j++)  
G[i][j]=M;  
for(i=0;i<n;i++)  
{  
fin>>m;  
for(j=0;j<m;j++)  
{  
fin>>k>>l;  
G[i][k-1]=l;  
}  
}  
for(i=0;i<n;i++)  
{  
flag[i]=0;  
s[i]=M;  
}  
cur=0;  
flag[cur]=1;  
s[cur]=0;  
p[cur]=0;  
for(i=1;i<n;i++)  
{  
for(j=0;j<n;j++)  
{  
if(flag[j]==0)  
{  
m=s[cur]+G[cur][j];  
if(m<s[j])  
{  
s[j]=m;  
p[j]=cur;  
}  
}  
}  
m=M;  
for(j=0;j<n;j++)  
{  
if(flag[j]==0)  
{  
if(s[j]<m)  
{  
m=s[j];  
cur=j;  
}  
}  
}  
flag[cur]=1;  
if(s[cur]==M)  
{  
//continue;  
p[cur]=0;  
for(j=0;j<n;j++)  
if(flag[j]==0)  
{  
s[j]=M;  
p[j]=0;  
flag[j]=1;  
}  
break;  
}  
}  
ofstream fout("out.txt");  
for(i=1;i<n;i++)  
{  
if(s[i]==M)  
{  
cout<<"从第1个点到第"<<i+1<<"的最短路为:M.\n";  
fout<<"从第1个点到第"<<i+1<<"的最短路为:M.\n";  
}  
else  
{  
cout<<"从第1个点到第"<<i+1<<"的最短路为:"<<s[i]<<".\n";  
cout<<"路径为:"<<i+1;  
fout<<"从第1个点到第"<<i+1<<"的最短路为:"<<s[i]<<".\n";  
fout<<"路径为:"<<i+1;  
k=p[i];  
cout<<" <-"<<k+1;  
fout<<" <-"<<k+1;  
while(k!=0)  
{  
k=p[k];  
cout<<" <-"<<k+1;  
fout<<" <-"<<k+1;  
}  
}  
cout<<endl<<endl;  
fout<<endl<<endl;  
}  
return 0;  
}  


测试数据：  
11  
2 2 2 4 8  
2 5 1 4 6  
2 7 9 1 1  
1 3 7  
2 9 1 4 5  
3 5 3 4 1 7 4  
3 4 7 9 3 10 1  
2 5 2 11 9  
2 6 6 8 7  
2 9 1 11 4  
1 9 2  


11表示有11个顶点的图  
2 2 2 4 8  
2表示第一个顶点射出2条线，2 2表示1->2的长度为2。。。。。。。。  

输出数据:  
从第1个点到第2的最短路为:2.  
路径为:2 <-1  

从第1个点到第3的最短路为:15.  
路径为:3 <-4 <-1  

从第1个点到第4的最短路为:8.  
路径为:4 <-1  

从第1个点到第5的最短路为:3.  
路径为:5 <-2 <-1  

从第1个点到第6的最短路为:10.  
路径为:6 <-9 <-5 <-2 <-1  

从第1个点到第7的最短路为:14.  
路径为:7 <-6 <-9 <-5 <-2 <-1  

从第1个点到第8的最短路为:11.  
路径为:8 <-9 <-5 <-2 <-1  

从第1个点到第9的最短路为:4.  
路径为:9 <-5 <-2 <-1  

从第1个点到第10的最短路为:15.  
路径为:10 <-7 <-6 <-9 <-5 <-2 <-1  

从第1个点到第11的最短路为:19.  
路径为:11 <-10 <-7 <-6 <-9 <-5 <-2 <-1