中国邮路问题中国邮递员问题⼀个邮递员送信，要⾛完他负责投递的所有街道（所有街道都是双向通⾏的且每条街道能够经过不⽌⼀次），完毕任务后回到邮局，应按如何的路线⾛，他所⾛的路程才会最短呢？解决⽅式1、图论建模因为街道是双向通⾏的，我们能够把它看成是赋权⽆向连通图，将路⼝模型为点，街道模型为边，街道的长度就是每条边的权值，问题转化为在图中求⼀条回路，使得回路的总权值最⼩。
1.1最理想的情况若图中有欧拉回路，由于欧拉回路通过全部的边，因此不论什么⼀个欧拉回路即为此问题的解。
1.2若G仅仅有两个Vi,Vj则有从Vi到Vj的欧拉迹，从Vj回到Vi则必须反复⼀些边，使反复边的总长度最⼩，转化为求从Vi到Vj的最短路径。
算法：1）找出奇点Vi,Vj之间的最短路径P；2）令G’ = G + P；3）G’为欧拉图，G’的欧拉回路即为最优邮路。
1.3普通情况，奇点数⼤于2的时，邮路必须反复很多其它的边。
Edmonds算法（匈⽛利算法）思想：步骤：1）求出G全部奇点之间的最短路径和距离；2）以G的全部奇点为结点（必为偶数），以他们之间的最短距离为节点之间边的权值，得到⼀个全然图G1；3）将M中的匹配边（Vi，Vj）写成Vi与Vj之间的最短路径经过的全部边集合Eij；4）令G’ = G U { Eij | (Vi,Vj)属于M}，则G’是欧拉图，求出最优邮路。
2、详细模块实现2.1最短路径⽤ Dijkstra算法计算Dijkstra算法是⼀种最短路径算法，⽤于计算⼀个节点到其他全部节点的最短路径。
2.1.1算法思想：按路径长度递增次序产⽣最短路径算法： 把V分成两组： 1）S：已求出最短路径的顶点的集合 2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序增加到S中，保证：1）从源点V0到S中各顶点的最短路径长度都不⼤于从V0到T中不论什么顶点的最短路径长度 2）每⼀个顶点相应⼀个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的仅仅包含S中顶点作中间顶点的最短路径长度2.1.2求最短路径步骤 1）初始时令 S={V0},T={ 其余顶点}，T中顶点相应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值；若不存在<V0,Vi>，d(V0,Vi)为∝ 2）从T中选取⼀个其距离值为最⼩的顶点W且不在S中，增加S 3）对S中顶点的距离值进⾏改动：若加进W作中间顶点，从V0到Vi的距离值缩短，则改动此距离值；反复上述步骤2、3，直到S中包括全部顶点，即W=Vi为⽌2.2图的连通性測试检測⽤户输⼊的图是否是连通图，不是的话没办法求解，提醒⽤户⼜⼀次输⼊。
中国邮路问题及解决方案中国邮递员问题一个邮递员送信，要走完他负责投递的全部街道（所有街道都是双向通行的且每条街道可以经过不止一次），完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？解决方案1、图论建模由于街道是双向通行的，我们可以把它看成是赋权无向连通图，将路口模型为点，街道模型为边，街道的长度就是每条边的权值，问题转化为在图中求一条回路，使得回路的总权值最小。
1.1最理想的情况若图中有欧拉回路，因为欧拉回路通过所有的边，因此任何一个欧拉回路即为此问题的解。
1.2若G只有两个奇点Vi,Vj则有从Vi到Vj的欧拉迹，从Vj回到Vi则必须重复一些边，使重复边的总长度最小，转化为求从Vi到Vj的最短路径。
算法：1）找出奇点Vi,Vj之间的最短路径P；2）令G’ = G + P；3）G’为欧拉图，G’的欧拉回路即为最优邮路。
1.3一般情况，奇点数大于2的时，邮路必须重复更多的边。
Edmonds算法（匈牙利算法）思想：步骤：1）求出G所有奇点之间的最短路径和距离；2）以G的所有奇点为结点（必为偶数），以他们之间的最短距离为节点之间边的权值，得到一个完全图G1；3）将M中的匹配边（Vi，Vj）写成Vi与Vj之间的最短路径经过的所有边集合Eij；4）令G’ = G U { Eij | (Vi,Vj)属于M}，则G’是欧拉图，求出最优邮路。
2、具体模块实现2.1最短路径用 Dijkstra算法计算Dijkstra算法是一种最短路径算法，用于计算一个节点到其它所有节点的最短路径。
2.1.1算法思想：按路径长度递增次序产生最短路径算法：把V分成两组：1）S：已求出最短路径的顶点的集合2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度2.1.2求最短路径步骤1）初始时令 S={V0},T={ 其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值；若不存在<V0,Vi>，d(V0,Vi)为∝2）从T中选取一个其距离值为最小的顶点W且不在S中，加入S3）对S中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值；重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止2.2图的连通性测试检测用户输入的图是否是连通图，不是的话没办法求解，提醒用户重新输入。
