这是一个图论的问题

一个图论问题~

这个在图论上是一个非常难的问题。
（对于数学问题来讲，非常难的意思就是基本上别想解了。）
图论中的“旅行商”问题与这个类似，但要比这个简单的多。旅行商问题中，只有每条线有权，也就是每个点的权是零，而且那个必须回来的阈值是无穷大，也就是一次游完所有地方。即使这样，旅行商问题也是非常困难的问题，是著名的 NP-hard 问题之一。所以你就可想而知你的问题了，基本上想都不要想了。

中国邮递员问题在证明最优解的充要条件时,我们通常都是把原问题化为在图上添加重边,使得原图变为欧拉图,然后使得添加的重边权数和最小.
在充分性证明时,假设最优图添加的重边集合是E1,对应图为G1.满足前面提到的两个充要条件的某种添加的重边集为E2,对应图为G2.那么我们的目标就是证明w(E1)=w(E2)
考虑边集E=E1∪E2\(E1∩E2).
那么如果E为空集,说明E1=E2,此时充分性成立.
如果E不为空集,则E生成的图G[E]中的各个顶点都为偶数.这是因为在G1和G2中,在某个顶点v上添加的边数的奇偶性和d(v)是相同的.(这条是证明重点,理解这条就能理解充分性的证明)
之后的问题就很简单,E中的顶点都为偶数,所以G[E]是若干个欧拉图的并. 又由于E1和E2中各自都不含圈(由E1,E2的定义可知). 所以G[E]中的圈都同时包含E1和E2中的边,又由充要条件2可以推得在G[E]的任何一个圈C中, E1和E2在其上的权重之和都等于w(C)的一半. 从而w(E1\(E1∩E2))=w(E2\(E1∩E2)),即w(E1)=w(E2).

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等

注意：你的指定点开始的问题，直接从把下面的东西看完后，应用（6）就可以解决，任意开始点的话，就把所有点都指定一下就行了。。。

再补充一个，这个算法一般图论书上都有，但是写的非常之高深莫测，看不懂的。。。建议去看清华大学的数据结构与算法这本书上的算法，（蓝色封皮的）

设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。
①初始化
初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。
②重复以下工作，按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
注意：
①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。

（3）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
源点，红点1，红点2，…，红点n，蓝点k
距离为：源点到红点n最短距离+<红点n,蓝点k>边长
为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度（简称估计距离）。
若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V-S}，则D[k]=SD(k)。
初始时，每个蓝点v的D[c]值应为权w<s，v>，且从s到v的路径上没有中间点，因为该路径仅含一条边<s，v>。
注意：
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键

（4）k扩充红点集s后，蓝点集估计距离的修改
将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。
对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。
所以，当length(P)=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。

（5）Dijkstra算法

Dijkstra(G，D，s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化操作
S={s}；D[s]=0； //设置初始的红点集及最短距离
for( all i∈ V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]； //设置i初始的估计距离为w<s，i>
//以下是扩充红点集
for(i=0;i<n-1;i++)do{//最多扩充n-1个蓝点到红点集
D[k]=min{D[i]：all i V-S}； //在当前蓝点集中选估计距离最小的顶点k
if(D[k]等于∞)
return； //蓝点集中所有蓝点的估计距离均为∞时，
//表示这些顶点的最短路径不存在。
S=S∪{k}； //将蓝点k涂红后扩充到红点集
for( all j∈V-S )do //调整剩余蓝点的估计距离
if(D[j]>D[k]+G[k][j])
//新红点k使原D[j]值变小时，用新路径的长度修改D[j]，
//使j离s更近。
D[j]=D[k]+G[k][j]；
}
}

（6）保存最短路径的Dijkstra算法
设置记录顶点双亲的向量P[0．．n-1]保存最短路径：
当顶点i无双亲时，令P[i]=-1。
当算法结束时，可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径，只不过路径方向正好与从s到i的路径相反。
。
Dijkstra算法的时间复杂度为O(n2)
参考资料：http://student.zjzk.cn/course_ware/data_structure/web/tu/tu7.5.2.htm

还个问题不太懂，交个朋友，以后方便交流。

wo
就看看

---

老边区15592064535： 关于离散数学中图论的一个问题题目:具有6个顶点,12条边的连通简单平面图中,每个面都是由()条边围成?? 急需解决... - ？
阿怕恩尔：[答案] 每个面都是三角形,所以都是三条边组成

老边区15592064535： 哥尼斯堡七桥问题 可以证明么? - ？
阿怕恩尔：[答案] 18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥,将河中的两个岛和河岸连结,如图1所示.城中的居民经常沿河过桥散步,于是提出了一个问题:能否一次走遍7座桥,而每座桥只许通过一次,最后仍回到起始地点.这就是七桥...

老边区15592064535： 一个图论问题 - ？
阿怕恩尔： 这个在图论上是一个非常难的问题.(对于数学问题来讲,非常难的意思就是基本上别想解了.) 图论中的“旅行商”问题与这个类似,但要比这个简单的多.旅行商问题中,只有每条线有权,也就是每个点的权是零,而且那个必须回来的阈值是无穷大,也就是一次游完所有地方.即使这样,旅行商问题也是非常困难的问题,是著名的 NP-hard 问题之一.所以你就可想而知你的问题了,基本上想都不要想了.

老边区15592064535： 9个人的集会中一定有3个人互相认识或4个人互相不认识 - ？
阿怕恩尔： 这各问题有点属于社会人际关系统计的范畴 可以这么解释 理论上俩个陌生人之间最多需要6层就可以认识对方 但是实际是5层就够 要把最后一层留给全世界每一秒都会降生的新生儿 因为他们只认识他们的母亲 9个人的聚会 每个人认识对方都不会超过6层 所以等到第9个人出现时 前面的一定会有两个人跟他认识 这是有三个人认识 .....这个问题牵涉了很多学科 我要在好好想想 lz再看看还有没有别的答案

老边区15592064535： 科尼斯堡七桥问题 - ？
阿怕恩尔： 柯尼斯堡七桥问题是图论中的著名问题.这个问题是基于一个现实生活中的事例:位于当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)有一条河,河中心有两个小岛.小岛与河的两岸有七条桥连接.在所有桥都只能走一遍的前提下,如何才能...

老边区15592064535： 如何看待哥尼斯堡七桥问题? - ？
阿怕恩尔： 18世纪时,欧洲有一个风景秀丽的小城哥尼斯堡,那里有七座桥.如图1所示:河中的小岛A与河的左岸B、右岸C各有两座桥相连结,河中两支流间的陆地D与A、B、C各有一座桥相连结.当时哥尼斯堡的居民中流传着一道难题:一个人怎样才...

老边区15592064535： 现有容量为30ml,100ml和120ml的杯子各一个,怎样利用这三个量杯量出110ml的水 - ？
阿怕恩尔： 先用30和100的量满,到入120的,将120的水倒掉,然后将剩下的10ml倒入120的杯子里,在用100的量满倒入120的杯子

老边区15592064535： 有6个人去参加集会,请证明至少有三个人互相认识? - ？
阿怕恩尔：[答案] 题目有问题吧...应该是证:请证明至少有三人互相认识或互相不认识.这是一道图论问题,方法是用红蓝二色染色.红色代表认识,蓝色代表不认识.即证明六点中的15条连线至少可以组成一个同色三角形.这是图论的基本问题,先取...

老边区15592064535： 一道图论问题.某公司在六个城市C1,C2,…,C6中都有分公司,从Ci到Cj的直接航程票价由下述矩阵的第(i,j)元素给出(∞表示无直接航路):0 50 ∞ 40 25 ... - ？
阿怕恩尔：[答案] 用Floyd算法求出各点到其他点的最短路径长度即可 矩阵如下 0 35 45 35 25 10 35 0 15 20 35 25 45 15 0 10 20 35 35 20 10 0 10 25 25 35 20 10 0 35 10 25 35 25 35 0 接下来会了吧.

老边区15592064535： 七桥问题怎么解 - ？
阿怕恩尔： 哥尼斯堡七桥问题 哥尼斯堡城是位于普累格河上的一座城市,今天属于俄罗斯加里宁格勒,以前是东普鲁士的土地.它包含两个岛屿及连接它们的七座桥.普累格河流经城区的这两个岛,岛与河岸之间架有六座桥,另一座桥则连接着两个岛.哥...