2 coconot coconot 于 2015.07.14 10:46 提问

指定有向带权图中的任意几点,如何求出是否存在通路以及通路的最短路径?

指定有向带权图中的任意几点,如何求出是否存在通路以及通路的最短路径?

1个回答

se7en_q
se7en_q   2015.07.14 15:12

这是一个简单的带权图
虽然这是一个无向的,但是主要还是方法。
面对这个问题主要还是先解决起点(设为a)到其他点的最短通路,直到找到你所指定的一点(设为z)
w(a,b)=4 w(a,d)=2 w(b,c)=3 w(d,e)=3 w(e.z)=1 w(c,z)=2

1、初始P={a},T={b,c,d,e,z} D(b)=4;D(c)=∞;D(d)=2;D(e)=∞;D(z)=∞;其中p表示求得最小距离的顶点集合,其中D(a)=0

            由此可以看出D(d)=2是距离a最近的,将它放到P集合中
            2、P={a,d},T={b,c,e,z}
                    D(x)=min{上一步计算的D(x),上一步新加到P集合的点到x的距离+新加的最短距离}
                    所以:
                    D(b)=min{4, ∞}=4;
                    D(c)=min{∞,∞}=∞;
                    D(e)=min{∞,2+3}=5;
                    D(z)=min{∞.∞}=∞;
                    由此可知D(b)是最小的,
            3、P={a,d,b},T={c,e,z}
                    D(c)=min{∞,D(b)+w(b,c)}=7;
                    D(e)=min{5,∞}=5;
                    D(z)=min{∞,∞}=∞;
                    将e放到P中依次类推,知道找到你选定的终点为止。
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
带权有向图最短路径
1、带权有向图最短路径 1)      适用条件&范围: a)   单源最短路径(从源点s到其它所有顶点v); b)   有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图) c)   所有边权非负(任取(i,j)∈E都有Wij≥0); 2)      算法描述: 在带权图中最常遇到的问题就是,寻找两点间的最短路径问题。   解决最短路径问题最著名的算法是Dj
任意竞赛图都有哈密顿path(A Tournament has a Hamiltonian path)
设G是竞赛图,即完全图的一个定向。则G必有哈密顿path. 证明: 反证。设n=|V|, 且P={1,2,3,…,k}(k<n)P=\{1,2,3,\dots,k\}(k<n)是G中的最长path. 则对任取的a∉Pa\notin P, 我们有下图 如果a和1a\textrm{和}1之间的边为(a,1)(a,1),那么把 aa 添加进P的开头就是一条比P更长的path,这样矛盾。同理
有向图中两个结点之间是否存在一条路径
给定有向图,设计一个算法,找出两个结点之间是否存在一条路径 public enum State { Unvisited,Visited,Visiting; } public  static boolean search(Graph g,Node start ,NLinkedList { //当作队列使用 LinkedList q=new LinkedList(); for
运用Floyd算法求得带权有向图任意两点间的最短路径C/C++
一、 算法过程1,从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i][j]=d,d表示该路的长度;否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i][j]
最短路径系列【最短路径、哈密顿路等】
http://www.cnblogs.com/zhexue/archive/2011/12/27/2303859.html 本文转载本人独立博客:http://zhexue.sinaapp.com/?p=13 最短路径问题,一个经典算法问题。本文粗略总结了一种常见的最短路径算法,以及几个最短路径变种问题的解法,其中包括哈密顿路。对于有向图或者无向图,假设有V个节点,E条边,G[Vi,Vj]表示
各种图回路性质及判定
一、哈密顿回路  1.哈密顿回路必须是封闭的环 2.是一个连通图,任意两点都可到达,经过图中所有的点一次且仅一次的回路. 二、欧拉回路(图的一笔画问题) 1.欧拉通路:存在这样一条路径,使其经过图G中所有的边一次  若该路径是一个环 就是欧拉回路 2. 无向图存在欧拉回路的充要条件 一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图。 无向图存
计算图顶点之间的通路数 和 连通性
图 通路数 连通性
带权有向图单源最短路径(Dijkstra算法)
单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。 一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。 假设P(i,j)={Vi.
判别无向图中任意两个顶点之间是否存在长度为K的简单路径
题 目: 判别无向图中任意两个顶点之间是否存在长度为K的简单路径。 初始条件: 1.采用邻接表作为存储结构。 2.编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。 3测试用例自己设计。 注释:简单路径,即其顶点序列中不含有重现的顶点
整数规划求解有向图最短路径问题环路解决方法
整数规划求解有向图最短路径问题环路解决方法 在有向图中,经常遇到给定起点和终点以及必经点,选择一条权重最小的路径这样的问题。这种问题可以看做是旅行商问题(tsp)的变种,tsp问题是一种组合爆炸问题,当规模变大时,时间耗费十分巨大。