求任意的两个城市之间的最短路径

★☆ 求任意的两个城市之间的最短路径
★☆ http://www.ok2002.com/cc_htm/ok2002com_of_cc_663.htm

#include<iostream.h>
#include<stdlib.h>
#define M 100  //最大顶点数
#define Mi 32767
typedef char TYPE;
typedef int adj;

typedef struct
{
     TYPE v[M];//顶点数组
     adj ar[M][M];//邻接矩阵
}ook;

int 
d1[M],
p1[M], 
d[M][M],
p[M][M];

void cre(ook *g,int n,int e)
{
   int j,i,k,w;//采用邻接矩阵表示法构造有向图的顶点数和边数
   for(i=1;i<=n;i++)//输入顶点信息
	   g->v[i]=(char)i;
   for(i=1;i<=n;i++)
	   for(j=1;j<=n;j++)
		   g->ar[i][j]=Mi;//初始化邻接矩阵
	   cout<<"请输入"<<e<<"条边的i、j及w："<<endl;
	   cout<<endl;
   
   for(k=1;k<=e;k++)
   {
	   cin>>i>>j>>w;
	   g->ar[i][j]=w;
   }
   cout<<"有向图的存储结构建立完毕！"<<endl;
}

void FD(ook *g,int n)
{
    int j,i,k;
    for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
	   {
          if(g->ar[i][j]!=Mi) 
             p[i][j]=j;
          else 
             p[i][j]=0;
          d[i][j]=g->ar[i][j];
       }

    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
			   if(d[i][k]+d[k][j]<d[i][j])
			   {
				   d[i][j]=d[i][k]+d[k][j];//修改长度
				   p[i][j]=p[i][k];
			   }
}

void main()
{
   ook *g;
   int m,n,e,v,w,k;
   int xz=1;
   g=(ook *)malloc(sizeof(ook));
   cout<<"请输入图中顶点个数和边数n,e:";
   cin>>n>>e;
   cre(g,n,e);//建立图的存储结构

   while(xz!=0)
   {
		cout<<"2.求任意的两个城市之间的最短路径"<<endl;
		cin>>xz;
        if(xz==2)
		{
             FD(g,n);//调用FD算法
			 cout<<"输入源点和终点:v,w:";
			 cin>>v>>w;
             k=p[v][w];//k为起点v的后继顶点
             if(k==0)
			 cout<<"顶点"<<v<<"到"<<w<<"无路径!"<<endl;
             else
			 {
				 cout<<"顶点"<<v<<"到"<<w<<"的路径是："<<v<<endl;
				 while(k!=w)
				 {
					 cout<<"->"<<k;
					 k=p[k][w];
				 }
				 cout<<"->"<<k;
				 cout<<"路径长度为:"<<d[v][w]<<endl;;
			 }
		}
		else if(xz==1)
		{
			cout<<"求单源路径，输入源点v:";
			cin>>v;
		}
   }
   cout<<"结束求最短路径!"<<v<<w<<endl;
}

//【www.ok2002.com C++程序设计】

	问题类型: 验证:
	主题[少于250字]：详细[少于5000字]：阅读C++代码有疑问,我们一起讨论:
	看看学C++的人问了哪些问题? OK2002.COM推出: 一起学C++ [阅读C++代码有疑问,我们一起讨论]


	相关源码: ☆ 求未知链表的中间位置算法： ☆ 猫吃老鼠，就是猴子选大王的改版，循环链表解决 ☆ C++编写约瑟夫环 ☆ strcpy函数的原型 ☆ 求1000!的未尾有几个0 ☆ 有数字1、2、3，能组成多少个互不相同且无重复数字的三位数？都是多少？最近更新 ※ //STL C++ 两个整型数组一同排序 ※ STL C++整型数组排序 ※ C++输出迭代器ostream_iterator ※ //C++交换整型数组元素程序源码 ※ //C++交换整型数组元素程序源码使用输出迭代器ostream_iterator ※ 初次成功地将单链表结点置入栈中 ※ C/C++程序广义表〖简化版〗 ※ //只让偶数入队列C++程序 ※ 只让字母入队列C++程序 ※ 翻转数组C++源码
	C++程序设计:OK2002.COM

更多C++代码请到C++源码目录页

网站空间

C++程序设计QQ群:64777950
Wheels on the bus Apple round apple red 苹果红...苹果圆...My little donkey 我的小毛驴 Hello song 我们一起唱HELLO歌
ABC song 我们一起唱ABC hush,little baby 安静...觉觉...小宝贝

更多动画 OK1500.COM

※ [1] C++程序设计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . WWW.OK2002.COM
※ [2] 英语儿歌[动画]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . WWW.OK1500.COM
※ [3]企业建站] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . WWW.OK1700.COM

合作意向 - web版QQ聊天器 - web版五笔在线输入

邮箱：webmaster

ok2002.com