关于最短路径的算法问题。

Question

题目描述

题目背景
首先地图上有40个点，把他们分成两组，第一组和第二组，每一组都有20个点。

现在将第一组的每一个点都设为起点，第二组的每一个点都设为终点

问题如下：

起点和终点两两一对，不出现重复，如何求得每一对点的路径之和最短？

题目来源及自己的思路

我的思路是对终点进行全排列，然后对每一种排列之后的结果一一进行比较，最终的路径之和最短的结果，可是我试过了不少的全排算法，都无法支持20个数的全排列。因此我的思路就此打断

你期待的结果是什么？

期待看到的结果是能够显示路径之和最短是多少以及具体的起点与终点的对应关系。

以下为模拟的示意图

Answer 1

题主，这个在图论当中叫做二分图，这个问题叫做二分图匹配。
如果仅仅是找到第一组到第二组的能够匹配的边数最多的情况，使用匈牙利算法；
而如果这些边带有权值需要求和最大、最小的情况，那么使用KM算法或者网络流。

具体还可以参考以下文章：
BYvoid的匈牙利算法和二分图带权匹配 KM算法与费用流模型建立。