急求~~~公司想算出一张任意两个城市之间的最廉航价路线表.试作出这样的表来.Dijkstra算法某公司在六个城市C1,C2,…,C6中都有分公司,从Ci到Cj的直接航程票价由下述矩阵的第(i,j)元素给出(

Question

急求~~~公司想算出一张任意两个城市之间的最廉航价路线表. 试作出这样的表来.
Dijkstra算法某公司在六个城市C1, C2, …, C6中都有分公司,从Ci到Cj的直接航程票价由下述矩阵的第(i, j)元素给出(∞表示无直接航路)：
0 50 ∞ 40 25 10
50 0 15 20 ∞ 25
∞ 15 0 10 20 ∞
40 20 10 0 10 25
25 ∞ 20 10 0 55
10 25 ∞ 25 55 0
该 公司想算出一张任意两个城市之间的最廉航价路线表. 试作出这样的表来.
结果就行!

Answer 1

C1-->C1:0
C1
C1-->C2:35
C1->C6->C2
C1-->C3:45
C1->C5->C3
C1-->C4:35
C1->C6->C4
C1-->C5:25
C1->C5
C1-->C6:10
C1->C6
C2-->C1:35
C2->C6->C1
C2-->C2:0
C2
C2-->C3:15
C2->C3
C2-->C4:20
C2->C4
C2-->C5:30
C2->C4->C5
C2-->C6:25
C2->C6
C3-->C1:45
C3->C5->C1
C3-->C2:15
C3->C2
C3-->C3:0
C3
C3-->C4:10
C3->C4
C3-->C5:20
C3->C5
C3-->C6:35
C3->C4->C6
C4-->C1:35
C4->C5->C1
C4-->C2:20
C4->C2
C4-->C3:10
C4->C3
C4-->C4:0
C4
C4-->C5:10
C4->C5
C4-->C6:25
C4->C6
C5-->C1:25
C5->C1
C5-->C2:30
C5->C4->C2
C5-->C3:20
C5->C3
C5-->C4:10
C5->C4
C5-->C5:0
C5
C5-->C6:35
C5->C4->C6
C6-->C1:10
C6->C1
C6-->C2:25
C6->C2
C6-->C3:35
C6->C4->C3
C6-->C4:25
C6->C4
C6-->C5:35
C6->C1->C5
C6-->C6:0
C6
这题是用程序写的,C++的程序附在下面
#include
int i,j,k,l,min,s;
int a[7],f[7],p[7],ans[7];
int g[7][7];
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
for(i=1;i<7;++i)
for(j=1;j<7;++j)scanf("%d",&g[i][j]);
for(i=1;i<7;++i)
{
for(j=1;j<7;++j)
{
a[j]=1000000;
p[j]=0;
f[j]=0;
}
a[i]=0;
for(j=1;j<7;++j)
{
min=1000000;
for(k=1;k<7;++k)
if((!p[k])&&(a[k] {
min=a[k];
l=k;
}
p[l]=1;
for(k=1;k<7;++k)
if(a[k]>a[l]+g[l][k])
{
a[k]=a[l]+g[l][k];
f[k]=l;
}
}
for(j=1;j<7;++j)
{
printf("C%d-->C%d:%d\n",i,j,a[j]);
printf("C%d",i);
s=0;
k=j;
for(;k;k=f[k])ans[++s]=k;
for(--s;s;--s)printf("->C%d",ans[s]);
printf("\n");
printf("\n");
}
}
return 0;
}