图的应用——最短路径

最短路径

  • 典型用途:交通问题。如:城市A到城市B有多条线路,但每条线路的交通费(或所需时间)不同,那么,如何选择一条线路,使总费用(或总时间)最少?
  • 问题抽象:在带权有向图中A点(源点)到达B点(终点)的多条路径中,寻找一条各边权值之和最小的路径,即最短路径。最短路径与最小生成树不同,路径上不一定包含n个顶点

两种常见最短路径问题


Dijkstra(迪杰斯特拉)算法 —— 单源最短路径

在这里插入图片描述

算法思想

把图中顶点集合分成两组:

第一组为已求出其最短路径的顶点集合S

第二组为尚未确定最短路径的顶点集合U

  1. 初始时,S只包含源点,S={v},U包含除v外的其他顶点;
  2. 从U中选取一个距离最小的顶点k,把k加入到S中;
  3. 以k作为新考虑的中间点,修改U中各顶点的距离;
  4. 重复步骤 2、3 直到所有顶点都包含在S中

算法实现

算法流程图

在这里插入图片描述

C++代码实现

void ShortestPath_DIJ(AMGraph G, int v0){
	// 用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 
	n = G.vexnum;  // G 中顶点个数
	for(v = 0; v < n; v++){
		// n 个顶点依次初始化
		S[v] = false;  // S 初始为空集
		D[v] = G.arcs[v0][v];  // 将v0到各个终点的最短路径长度初始化  
		if(D[v] < MaxInt) Path[v] = v0;  // v0和v之间有弧,将v的前驱置为v0
		else Path[v] = -1;  // 如果v0和v之间无弧,则将v的前驱置为-1
	}
	S[v0] = true;  // 将v0加入S
	D[v0] = 0;  // 源点到源点的距离为0

	/*―开始主循环,每次求得v0到某个顶点v的最短路径,将v加到S集―*/
	for(i = 1; i < n; i++){
		// 对其余n-1个顶点,依次进行计算
		min = MaxInt;
		for(w = 0; w < n; w++)
			if(!S[w] && (D[w] < min)){
				v = w;
				min = D[w];  // 选择一条当前的最短路径,终点为v
			}
		S[v] = true;  // 将v加入S
		for(w = 0; w < n; w++)  // 更新从v0出发到集合V−S上所有顶点的最短路径长度
			if(!S[w] && ((D[v] + G.arcs[v][w]) < D[w])){
				D[w] = D[v] + G.arcs[v][w];  // 更新D[w]
				Path[w] = v;  // 更新w的前驱为v
			}
	}
}


Floyd(弗洛伊德)算法 —— 所有顶点间的最短路径

每一对顶点之间的最短路径

方法一:每次以一个顶点为源点,重复执行Dijkstra算法n次—— T(n)=O(n³)

方法二:弗洛伊德(Floyd)算法

算法思想:逐个顶点试探法

算法思想

  • 初始时设置一个n阶方阵,令其对角线元素为0,若存在弧<Vi,Vj>,则对应元素为权值;否则为∞
  • 逐步试着在原直接路径中增加中间顶点,若加入中间点后路径变短,则修改之;否则,维持原值。
  • 所有顶点试探完毕,算法结结束
在这里插入图片描述

算法实现

typedef int Pathmatirx[MAXVEX][MAXVEX]
typedef int ShortPathTable[MAXVEX][MAXVEX]

/*- Floyd算法,求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w] -*/
void ShrotestPath_Floyd(MGraph G, Pathmatirx* P, ShortPathTable* D){
	int v, w, k;
	for(v = 0; v < G.numVertexes; ++v){
		// 初始化D与P
		for(w = 0; w < G.numVertexes; ++w){
			(*D)[v][w] = G.matirx[v][w];  // D[v][w]值即为对应点间的权值
			(*P)[v][w] = w;  // 初始化P

		}
	}

	for(k = 0; k < G.numVertexes; ++k)
		for(v = 0; v < G.numVertexes; ++v)
			for(w = 0; w < G.numVertexes; ++w)
				if((*D)[v][w] > (*D)[v][k] + (*D)[k][w]){
					// 如果经过下标为k顶点路径比原两点间路径更短
					// 将当前两点间权值设为更小的一个
					(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
					(*P)[v][w] = (*P)[v][k];  // 路径设置为经过下标为k的顶点
				}
}

正文完