中国邮递员问题
一个邮递员送信，要走完他负责投递的所有街道（所有街道都是双向通行的且每条街道能够经过不止一次），完毕任务后回到邮局，应按如何的路线走，他所走的路程才会最短呢？
解决方式
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）先查找图中看是否有单点，假设存在，不连通，返回false；
2）对全部的顶点測试，假设存在顶点既不是单点，也不在连当前连通顶点集中，则表示存在多个连通分支，返回false；
2.3计算奇点个数，处理奇点，利用奇点之间的完美匹配来确定反复边，使欧拉图具有最优邮路
2.4用Fleury算法求最短欧拉回游
如果迹wi=v0e1v1…eivi已经选定，那么按下述方法从E-｛e1,e2,…,ei｝中选取边ei+1:
1） ei+1与vi+1相关联；
2）除非没有别的边可选择，否则 ei+1不能是Gi=G-｛e1,e2,…,ei｝的割边。
3）当(2)不能运行时，算法停止。
代码没有弄完，看这个：
http://www.cnblogs.com/guocai/archive/2012/07/08/2581979.html