Shortest Path

最短路径

基本概念

最短路径(Shortest Path)

最短路径问题是图论中的一个经典问题，即求图中源点到终点之间的最短路径。在无权图中，从一个顶点到另一个顶点的最短路径为分支数目最少的一条路径，而在有权图中，考虑的是路径上的权重之和最小的路径，和最小生成树问题一样，图中可能存在权重相同的边，导致问题解不唯一。最短路径问题应用到现实中，例如交通系统、网络、费用问题等都可以使用最短路径解决，可以分为单源和多源，单源为图中一个顶点到其余顶点的最短路径，多源为任意两个顶点之间的路径，其中单源无负权边采用Dijkstra算法，单源负权边采用Bellman-Ford算法，多源采用Floyd算法。

---

Dijkstra算法

Dijkstra算法采用贪心策略，将顶点 V 划分为两个集合已求解集 S 和未求解集 V - S ，不断从 V - S 寻找距离起始点最短路径的点，当所有边权值都为正数时，每一轮将 V - S 集合中距离源点最近的点被纳入已求解顶点集，因为边为正数，可以证明无法以其它顶点为中转点找到更小的路径，Dijkstra算法正是通过这种性质来寻找最短路径，但图中出现边权为负数，这种性质就失效了，因此Dijkstra不能适用于负权图。

算法思想

初始化 S 集合为源点， V-S 集合为除源点以外的顶点，并且记录顶点距离，若和源点有领接边，则距离为领接边的权重，否则为 ∞ 。

每一轮选择最短距离的顶点 min ，将该顶点纳入已求解集中，表示到该顶点的最短路径已经找到，可以证明无法通过其余顶点作为中转点找到更短的路径，接着更新顶点距离，因为到 min 的最短路径已经求得，可以通过 min 来作为中转点进行更新，假如 k 为 V-S 中的一个顶点，从源点到 min 距离加上从 min 到的 k 的距离可能小于从源点到 k 的距离，如果小于则进行更新。

重复以上步骤，直到所有顶点被加入 S。

示例

首先准备三个向量: Final、Pre、Dist，Final 记录源点到该顶点的最短路径是否求得， Pre 记录到该顶点的前驱结点， Dist 记录到该顶点的权值，Final 的初始化为：除了源点初始化为 T ，其余顶点初始化为 F ， Pre 的初始化为：其余顶点到源点是否有领接边，如果有则为源点，否则记-1， Dist 的初始化为：其余顶点到源点的距离，如果有则为对于距离，否则记 ∞ 。

选择顶点 C ，从 A 到 C 的最短路径已经求得，由于都是正权值，不会存在另一条路径比该路径更短，接着将 C 作为中转点，可以发现 {A, C}{10} + {C,D}(50) < {A, D}(∞) ，到顶点 D 的路径改为60，其前驱为 C 顶点，将其更新。

选择 E 结点， A 到 E 的最短路径已求得，将E作为中转点， {A, E}(30) + {E, F}(60) < {A, F}(100)、{A, E}(30) + {E, D}(20) < {A, D}(60) ，将其更新。

选择 D 结点， A 到 D 的最短路径已求得，将 D 作为中转点，可以发现 {A, D}(50) + {D, F}(10) < {A, F}(90) ，将到 F 的前驱改为 D，路径值改为60。

由于结点 F 没有出度边，因此没有更新，而最后一个结点 B 没有入度边，是不可达的，因此最后结果和本轮一致。 Pre 记录了到达该点最短路径的前驱，因此通过前驱不断先前寻找，即可得到完整的最短路径。

代码实现

/*
typedef struct {
  VerTexType vexs[MAX];//顶点表
  ArcType m[MAX][MAX];//矩阵
  int vexnum, arcnum;//顶点数和边数
}AMG;
*/

int getMin(const AMG *G, const bool *final, const int *dist) {
  int min = INT_MAX, idx = -1;
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	if (!final[i] && dist[i] < min) {
	  min = dist[i];
	  idx = i;
	}
  }
  return idx;
}

void dijkstra(const AMG *G, VerTexType start) {
  int v = locateVex(G,start);
  bool *final = (bool*)malloc(sizeof(bool) * G -> vexnum);
  int *pre = (int*)malloc(sizeof(int) * G -> vexnum);
  int *dist = (int*)malloc(sizeof(int) * G -> vexnum);
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	final[i] = false;
	if (G -> m[v][i] && G -> m[v][i] != INT_MAX) {
	  pre[i] = v;
	  dist[i] = G -> m[v][i];
	} else {
	  pre[i] = -1;
	  dist[i] = INT_MAX;
	}
  }
  final[v] = true;
  dist[v] = 0;
  for (int i = 0 ; i < G -> vexnum - 1 ; ++i) {
	int min = getMin(G, final, dist);
	final[min] = true;
	for (int k = 0 ; k < G -> vexnum ; ++k) {
	  if (!final[k] && G ->m[min][k] != INT_MAX && dist[min] + G -> m[min][k] < dist[k]) {
		dist[k] = dist[min] + G -> m[min][k];
		pre[k] = min;
	  }
	}
  }
 // printPath(G, pre, dist);
}

运行结果

---

Floyd算法