数据结构中的求两点之间的最短距离的程序应该怎么写啊
我不知道该怎么下手
请大家不要笑话我
给你个题参考(不过我不知道怎么贴图)
.最短路径的求解问题(30分):
在某个国家有16个城市,用代号A—P表示(如下页图),图中线段表示两地之间距离,带箭头的线段表示路线有方向性,即反方向不能通行,试编写一程序,求解任意两地之间最短路程,并输出具体路径。
例:
输入:两地代号A O
输出:
/*------------------------------------------------------------------------------------------------------
# include<iostream>
using namespace std;
int main()
{int i,j,k;
int a[16][16]={//初始化邻接矩阵
{0 ,7 ,10,99,99,8 ,99,99,99,99,99,99,99,99,99,99},//0
{7 ,0 ,99,99,9 ,99,99,99,99,99,99,99,99,99,99,99},//1
{10,99,0 ,6 ,99,99,99,99,99,99,99,99,99,9 ,99,13},//2
{99,99,6 ,0 ,10,99,99,99,99,99,99,99,99,99,99,99},//3
{99,9 ,99,99,0 ,5 ,99,99,9 ,99,99,99,99,13,99,99},//4
{8 ,99,99,99,5 ,0 ,8 ,99,99,99,99,99,99,99,99,99},//5
{99,99,99,99,7 ,8 ,0 ,7 ,11,99,99,99,99,99,99,99},//6
{99,99,99,99,99,99,7 ,0 ,8 ,99,99,99,99,99,99,99},//7
{99,99,99,99,9 ,99,99,8 ,0 ,10,99,99,11,99,99,99},//8
{99,99,99,99,99,99,99,99,99,0 ,12,99,99,99,99,99},//9
{99,99,99,99,99,99,99,99,99,12,0 ,14,99,99,99,99},//10
{99,99,99,99,99,99,99,99,99,99,99,0 ,9 ,99,5 ,99},//11
{99,99,99,99,99,99,99,99,11,99,99,9 ,0 ,7 ,99,99},//12
{99,99,99,99,13,99,99,99,99,99,99,99,7 ,0 ,99,8 },//13
{99,99,99,99,99,99,99,99,99,99,99,5 ,99,99,0 ,4 },//14
{99,99,13,99,99,99,99,99,99,99,99,6 ,99,99,4 ,0 }};//15
int d[16][16];int path[16][16];
for(i=0;i<16;i++)//初始化路程矩阵
for(j=0;j<16;j++)
d[i][j]=a[i][j];
for(i=0;i<16;i++)//初始化路径矩阵
for(j=0;j<16;j++)
if((i!=j)&&(a[i][j]!=99))path[i][j]=i;else path[i][j]=-1;
for(k=0;k<16;k++)//依次在空集中加入结点0~6.即考虑新结点对全部结点的影响
for(i=0;i<16;i++)
for(j=0;j<16;j++)
if((d[i][k]+d[k][j])<d[i][j])//如果加入新的一个结点后,路程变短了
{
d[i][j]=d[i][k]+d[k][j];//在路程矩阵中更新路程为比较小的值
path[i][j]=path[k][j];//更新路径矩阵
}
int startnod;int endnod;int midnod1;int midnod2;char ch;
cout<<"请输入起始地点:";
cin>>ch;
switch(ch)
{
case 'A':
case 'a':startnod=0;break;
case 'B':
case 'b':startnod=2;break;
case 'C':
case 'c':startnod=4;break;
case 'D':
case 'd':startnod=13;break;
case 'E':
case 'e':startnod=5;break;
case 'F':
case 'f':startnod=8;break;
case 'G':
case 'g':startnod=12;break;
case 'H':
case 'h':startnod=7;break;
case 'I':
case 'i':startnod=15;break;
case 'J':
case 'j':startnod=6;break;
case 'K':
case 'k':startnod=3;break;
case 'L':
case 'l':startnod=10;break;
case 'M':
case 'm':startnod=11;break;
case 'N':
case 'n':startnod=14;break;
case 'O':
case 'o':startnod=1;break;
case 'P':
case 'p':startnod=9;break;
}
midnod1=startnod;
cout<<"请输入目的地点:";
cin>>ch;
switch(ch)
{
case 'A':
case 'a':endnod=0;break;
case 'B':
case 'b':endnod=2;break;
case 'C':
case 'c':endnod=4;break;
case 'D':
case 'd':endnod=13;break;
case 'E':
case 'e':endnod=5;break;
case 'F':
case 'f':endnod=8;break;
case 'G':
case 'g':endnod=12;break;
case 'H':
case 'h':endnod=7;break;
case 'I':
case 'i':endnod=15;break;
case 'J':
case 'j':endnod=6;break;
case 'K':
case 'k':endnod=3;break;
case 'L':
case 'l':endnod=10;break;
case 'M':
case 'm':endnod=11;break;
case 'N':
case 'n':endnod=14;break;
case 'O':
case 'o':endnod=1;break;
case 'P':
case 'p':endnod=9;break;
}
midnod2=endnod;
cout<<"最短路程:"<<d[startnod][endnod]<<endl;
cout<<"经过的路径:";
switch(startnod)
{
case 0:cout<<"A";break;
case 1:cout<<"O";break;
case 2:cout<<"B";break;
case 3:cout<<"K";break;
case 4:cout<<"C";break;
case 5:cout<<"E";break;
case 6:cout<<"J";break;
case 7:cout<<"H";break;
case 8:cout<<"F";break;
case 9:cout<<"P";break;
case 10:cout<<"L";break;
case 11:cout<<"M";break;
case 12:cout<<"G";break;
case 13:cout<<"D";break;
case 14:cout<<"N";break;
case 15:cout<<"I";break;
}
if(startnod!=endnod){//若不是原地踏步...
do
{ while(path[midnod1][midnod2]!=midnod1)
midnod2=path[midnod1][midnod2];//第一次循环时,midnod2是起点的下一个结点
cout<<"-->";
switch(midnod2)
{
case 0:cout<<"A";break;
case 1:cout<<"O";break;
case 2:cout<<"B";break;
case 3:cout<<"K";break;
case 4:cout<<"C";break;
case 5:cout<<"E";break;
case 6:cout<<"J";break;
case 7:cout<<"H";break;
case 8:cout<<"F";break;
case 9:cout<<"P";break;
case 10:cout<<"L";break;
case 11:cout<<"M";break;
case 12:cout<<"G";break;
case 13:cout<<"D";break;
case 14:cout<<"N";break;
case 15:cout<<"I";break;
}
midnod1=midnod2;midnod2=endnod;
}while(midnod1!=endnod);}
getchar();getchar();
return 0;
}