| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1482 人关注过本帖
标题:求最短距离的问题,谢谢
只看楼主 加入收藏
萧天
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-5-9
收藏
 问题点数:0 回复次数:5 
求最短距离的问题,谢谢
我刚学习数据结构,什么都不懂,有谁能帮我一下,
数据结构中的求两点之间的最短距离的程序应该怎么写啊
我不知道该怎么下手
请大家不要笑话我
搜索更多相关主题的帖子: 短距离 
2006-05-09 13:07
菜鸟上路
Rank: 4
等 级:贵宾
威 望:14
帖 子:1120
专家分:0
注 册:2006-3-21
收藏
得分:0 
???楼主是说图还是树什么的

2006-05-09 15:50
unicorn
Rank: 4
等 级:贵宾
威 望:14
帖 子:1066
专家分:0
注 册:2005-10-25
收藏
得分:0 

看看哈夫曼树吧


unicorn-h.spaces. ◇◆ sava-scratch.spaces.  noh enol ! pue pu!w hw u! shemle aq ll!m noh 
2006-05-09 15:55
萧天
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-5-9
收藏
得分:0 

很开心了,还有人回啊
我指的是图中两点之间的最短距离
我到现在还没做出来呢

2006-05-14 12:14
菜鸟上路
Rank: 4
等 级:贵宾
威 望:14
帖 子:1120
专家分:0
注 册:2006-3-21
收藏
得分:0 
这个我也没做啊,思路应该是:
先给定图中的两个顶点,然后再由其中一个顶点进行遍历(关于什么遍历,自己选),当遇到另一个顶点就停止,遍历的时候统计每条路径的权值之和,然后比较大小,得到路径。

2006-05-14 13:06
akadi
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2006-5-11
收藏
得分:0 

给你个题参考(不过我不知道怎么贴图)
.最短路径的求解问题(30)

在某个国家有16个城市,用代号A—P表示(如下页图),图中线段表示两地之间距离,带箭头的线段表示路线有方向性,即反方向不能通行,试编写一程序,求解任意两地之间最短路程,并输出具体路径。

例:

输入:两地代号A O

输出:7 A->0

/*------------------------------------------------------------------------------------------------------

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

2006-05-14 20:13
快速回复:求最短距离的问题,谢谢
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016159 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved