求有向图两个顶点间的最短路径的方法，用简单语言或举例描述。
求有向图两个顶点间的最短路径的方法，用简单语言或举例描述。 30
在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。交通网络可以用带权图表示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。　　以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径。　　最短路径问题的提法很多。在这里仅讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点S∈V到G中其余各顶点的最短路径。　　例如：下图(有向图G14)，假定以v1为源点，则其它各顶点的最短路径如下表所示：　　　　　　　　　　　　　　　　　　　　　　图 G14 　　从有向图可看出，顶点v1到v4的路径有3条：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4 )，其路径长度分别为：15,20和10。因此v1到v4的最短路径为(v1,v3,v2,v4 )。　　为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。　　那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉(Dijkstra)提出按路径长度递增产生诸顶点的最短路径算法，称之为迪杰斯特拉算法。　　迪杰斯特拉算法求最短路径的实现思想是：设有向图G=(V,E)，其中，V={1,2,…,n}，cost是表示G的邻接矩阵，cost[i][j] 表示有向边&i,j&的权。若不存在有向边&i,j&，则cost[i][j]的权为无穷大(这里取值为32767)。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含顶点v1。数组dist记录从源点到其他各顶点当前的最短距离，其初值为dist[i]=cost[v1][i]，i=2,…,n。从S之外的顶点集合V-S 中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S 中的顶点，把w加入集合S中调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v] 和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。　　最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到 V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i] 表示从源点到顶点i之间的最短路径的前驱顶点。
其他回答 (1)
图论，数据结构教材中有
相关知识等待您来回答
编程领域专家
& &SOGOU - 京ICP证050897号提问回答都赚钱
> 问题详情
对于下面两个图，分别求：
(1)每个顶点的度，有向图还要求入度和出度。
(2)给出一条从V0到V3的简单路径。
悬赏：0&&答案豆&&&&提问人：匿名网友&&&&提问收益：0.00答案豆&&&&&&
对于下面两个图，分别求： & & & &(1)每个顶点的度，有向图还要求入度和出度。 & &(2)给出一条从V0到V3的简单路径。 & &(3)给出图的邻接矩阵。 & &(4)给出图的邻接表。
发布时间：&&截止时间：
网友回答&(共0条)
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&10.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&10.00元收益
回答悬赏问题预计能赚取&2.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&10.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&10.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&2.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&2.00元收益
回答悬赏问题预计能赚取&20.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&22.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&22.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
你可能喜欢的
[] [] [] [] [] [] [] [] [] [] [] []
请先输入下方的验证码查看最佳答案
图形验证：8.3&求有向图的简单路径
#include&stdio.h&
#include&malloc.h&
#define MAXV 100
//以下定义邻接矩阵类型
typedef struct
&&&&&&&&&&
//顶点编号
//顶点其余的信息 &
typedef struct
edges[MAXV][MAXV];&& //邻接矩阵
n,e;&&&&&&&&&&&&&&&&
//顶点数，弧数
&VertexType
vexs[MAXV];&& //存放顶点信息
//一下定义邻接表类型
typedef struct
ANode&&&&&
//弧的节点结构类型
//该弧的终点位置
&struct ANode *
&&&&&&&&&&&
//弧的相关信息
typedef struct
Vnode&&&&&&
//邻接表头结点类型
&&&&&&&&&&&
//顶点信息
*&& //指向第一条弧
typedef VNode& AdjList[MAXV];
typedef struct
int visited[MAXV];
void PathAll1(ALGraph *G,int u,int v,int path[],int i)
//输出u到v所有简单的路径
&ArcNode *p;
&visited[u]=1;
&p=G-&adjlist[u].
&&if(n==v)
&&&path[i+1]=v;
&&&for(j=0;j&=i+1;j++)
printf("%3d",path[j]);
&&&&&&&&&&&
printf("\n");
&&else if(visited[n]==0)
&&&path[i+1]=n;
&&&PathAll1(G,n,v,path,i+1);
&visited[u]=0;
void PathAll2(ALGraph *G,int u,int v,int l,int path[],int
d)& //输出从u到v长度为l的所有简单路径，d初值为-1
&ArcNode *p;
&visited[u]=1;
&path[d]=u;
&if(u==v&&d==l)
&&for(i=0;i&=d;i++)
printf("%3d",path[i]);
printf("\n");
&p=G-&adjlist[u].
&&if(visited[m]==0)
PathAll2(G,m,v,l,path,d);
&visited[u]=0;
int ShortPath(ALGraph *G,int u,int v,int path[])&
//求u到v的最短路径&
//当前顶点编号
//当前顶点的层次
//当前顶点的前一个节点编号
&}qu[MAXV];
&int front=-1,rear=-1,k,i,j,
&ArcNode *p;
&visited[u]=1;
&qu[rear].vno=u;
&qu[rear].level=0;
&qu[rear].parent=-1;
&while(front&rear)
&&front++;
&&k=qu[front].
&&lev=qu[front].
&&if(k==v)
&&&while(j!=-1)
&&&&path[lev-i]=qu[j].
&&&&j=qu[j].
&&p=G-&adjlist[k].
&&while(p)
&&&if(visited[p-&adjvex]==0)
&&&&visited[p-&adjvex]=1;
&&&&rear++;
&&&&qu[rear].vno=p-&
&&&&qu[rear].level=lev+1;
&&&&qu[rear].parent=
&return 0;
void MatToList(MGraph g , ALGraph&
*&G)&&&&&&&
//将邻接矩阵 g 转换为邻接表 G
&int i,j,n=g.n;
&ArcNode *p;
&G=(ALGraph *)malloc(sizeof(ALGraph));
&for(i=0;i&n;i++)
G-&adjlist[i].firstarc=NULL;
for(i=0;i&n;i++)
for(j=n-1;j&=0;j--)
if(g.edges[i][j])
&p=(ArcNode *)malloc(sizeof(ArcNode));
&p-&adjvex=j;
&p-&info=g.edges[i][j];
&p-&nextarc=G-&adjlist[i].
&G-&adjlist[i].firstarc=p;
void DispAdj(ALGraph
//输出邻接表
&ArcNode *p;
&for(i=0;i&G-&n;i++)
&&p=G-&adjlist[i].
printf("%3d:",i);
&&while(p)
&&&printf("%3d",p-&adjvex);
&&printf("\n");
int main()
&int u=5,v=2,d=3;
&int path[MAXV];
&ALGraph *G;
&G=(ALGraph *)malloc(sizeof(ALGraph));
&int A[MAXV][6]={
&&{0,1,0,1,0,0},
&&{0,0,1,0,0,0},
&&{1,0,0,0,0,1},
&&{0,0,1,0,0,1},
&&{0,0,0,1,0,0},
&&{1,1,0,1,1,0}
&for(i=0;i&g.n;i++)
for(j=0;j&g.n;j++)
g.edges[i][j]=A[i][j];
&& MatToList(g,G);
&& printf("图G的邻接表：\n");
&& DispAdj(G);
&& printf("\n");
for(i=0;i&g.n;i++)
visited[i]=0;
printf("从%d到%d的所有路径：\n",u,v);
&& path[0]=u;
&& visited[u]=1;
&& PathAll1(G,u,v,path,0);
&& printf("\n");
for(i=0;i&g.n;i++)
visited[i]=0;
printf("从%d到%d的所有长度为%d的路径：\n",u,v,d);
PathAll2(G,u,v,d,path,-1);printf("\n");
for(i=0;i&g.n;i++)
visited[i]=0;
printf("从%d到%d的最短路径：\n",u,v);
for(i=0;i&g.n;i++)
visited[i]=0;
&& j=ShortPath(G,u,v,path);
for(i=0;i&=j;i++)
printf("%3d",path[i]);
&& printf("\n\n");
&& return 0;
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。2014华师远程数据结构在线作业_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
2014华师远程数据结构在线作业
上传于||暂无简介
阅读已结束，如果下载本文需要使用
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩10页未读，继续阅读
你可能喜欢已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,_百度作业帮
已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
初始化d[i]为无穷大,由于从v4开始,所以将d4=0,标记v4已选择.下面开始Dijkstra算法：和v4相连的且未标记的点有v2和v6,这样更新d2=20,d6=15,选择未标记所有点中最小的d6=15,标记v6已选择,这样我们算出了v4->v6最短距离d6=15；从v6开始,和v6相连的且未标记的是v2,此时算d6+6=21>20,所以不更新d2,选择未标记所有点中最小的d2=20,标记v2已选择,这样算出了v4->v2最短距离d2=20；从v2开始,和v2相连的且未标记的有v1和v5,d1=d2+10=30,d5=d2+30=50,选择未标记所有点中最小的d1=30,标记v1已选择,这样我们算出了v4->v1最短距离d1=30；从v1开始,和v1相连的且未标记的有v3,d3=d1+15=45,选择剩下没被选的所有点的最小的d3=45(d5=50),标记v3已选择,这样我们算出了v4->v3最短距离d3=45从v3开始,没有出去的路径,不更新距离,选择剩下没被选的所有点的最小的d5=50,标记v5已选择,这样我们算出了v4->v5最短距离d5=50.此时所有的点都被访问,结束.注：上面的标记点已选择注意下,在算法的实现中用的是将所有的点放入队列中,一旦一个点被选择就是说求出了最短距离,就从此队列删除该点,一直到此队列为空,结束算法,我写标记只是为了方便理解.希望能帮你清晰了解Dijkstra算法,图论中很重要的算法之一.