数据结构（十四）最短路问题

最短路径问题

1. 概述

1. 抽象

在网络（带权图）中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径

• 这条路径就是两点之间的最短路径（ShorttestPath）
• 第一个顶点为源点（Source）
• 最后一个顶点为终点（Destination）

2. 分类

• 单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
  • （有向）无权图
  • （有向）有权图
• 多源最短路径问题：求任意两顶点间的最短路径

2. 无权图的单源最短路算法

按照递增（非递减）的顺序找出到各个顶点的最短路

void Unweighted( Vertex s){
    queue<Vertex> q;
    q.push(s);
    wile(!q.empty()){
        v = q.front(); q.pop();
        for( V 的每个临界点 W){
            dist[W] = dist[v] + 1; // 当前距离上一距离 + 1
            path[W] = v;  // s 到 w 的必经顶点就是前一个顶点 v
            q.push(W);
        }
    }
}

3. 有权图的单源最短路算法

Dijkstra 算法

• 令 S = {源点s + 已经确定了最短路径的顶点 v $i_{}$i​}
• 对任一未收录的顶点 v，定义 dist[v] 为 s 到 v 的最短路径长度，但该路径仅经过 S 中的顶点。即路径 {s→(v $i_{}$i​∈S)→v} 的最小长度
• 若路径是按照递增（非递减）的顺序生成的，则
  • 真正的最短路必须只经过 S 中的顶点
  • 每次从未收录的顶点中选一个 dist 最小的收录
  • 增加一个 v 进入 S，可能影响另外一个 w 的 dist 值
    • dist[w] = min{dist[w],dist[v] + <v,w>的权重}

void Dijkstra( Vertex s ){
    while(1){
        V = 未收录顶点中dist最小值;
        if( 这样的V不存在 )
            break;
        collected[V] = true;
        for( V 的每个邻接点 W )
            if( collected[W] == false )
                if(dist[V] + E<V,W> < dist[W]){
             		dist[W] = dist[V] + E<V,W>;
                    path[W] = V;
                }
    }
}

取出未收录顶点中dist最小值 和 更新dist[W]的操作可以考虑两种方法：

1. 直接扫描所有未收录顶点 ——O(|V|)

   T = O(|V| $2^{}$2 + |E|) ——稠密图效果更好

2. 将dist存在最小堆中 ——O(log|V|)

   更新dist[w]的值 —O(log|V|)

   T = O(|E|log|V|) —— 稀疏图效果更好

#include<iostream>
#include<stdlib.h>
#define Inf 1000000
#define Init -1
#define MaxVertex 100
typedef int Vertex;
int G[MaxVertex][MaxVertex];
int dist[MaxVertex];  // 距离 
int path[MaxVertex];  // 路径 
int collected[MaxVertex];  // 被收录集合 
int Nv;   // 顶点 
int Ne;   // 边 
using namespace std;

// 初始化图信息 
void build(){
	Vertex v1,v2;
	int w;
	cin>>Nv;
	// 初始化图 
	for(int i=1;i<=Nv;i++)
		for(int j=1;j<=Nv;j++)
			G[i][j] = 0;
	// 初始化路径 
	for(int i=1;i<=Nv;i++)
		path[i] = Init;
	// 初始化距离
	for(int i=0;i<=Nv;i++)
		dist[i] = Inf;
	// 初始化收录情况 
	for(int i=1;i<=Nv;i++)
		collected[i] = false;
	cin>>Ne;
	// 初始化点
	for(int i=0;i<Ne;i++){
		cin>>v1>>v2>>w;
		G[v1][v2] = w;  // 有向图 
	}
}

// 初始化距离和路径信息 
void crate(Vertex s){
	dist[s] = 0;
	collected[s] = true;
	for(int i=1;i<=Nv;i++)
		if(G[s][i]){
			dist[i] = G[s][i];
			path[i] = s;
		}
}

// 查找未收录顶点中dist最小者
Vertex FindMin(Vertex s){
	int min = 0;  // 之前特地把 dist[0] 初始化为正无穷 
	for(Vertex i=1;i<=Nv;i++)
		if(i != s && dist[i] < dist[min] && !collected[i])
			min = i;
	return min;
}


void Dijkstra(Vertex s){
	crate(s); 
	while(true){
		Vertex V = FindMin(s);   // 找到 
		if(!V)
			break;
		collected[V] = true;  //收录
		for(Vertex W=1;W<=Nv;W++)
			if(!collected[W] && G[V][W]){  // 如果未被收录
				if(dist[V] + G[V][W] < dist[W]){
					dist[W] = G[V][W] + dist[V];
					path[W] = V;
				}
			}
	}
}

void output(){
	for(int i=1;i<=Nv;i++)
		cout<<dist[i]<<" ";
	cout<<endl;
	for(int i=1;i<=Nv;i++)
		cout<<path[i]<<" ";
	cout<<endl;
}


int main(){
	build();
	Dijkstra(1);
	output();
	return 0;
}

4. 多源最短路算法

• 直接将单源最短路算法调用|V|遍

  T = O(|V| $3^{}$3 + |E|×|V|) ——对于稀疏图效果好

• Floyd 算法

  T = O(|V| $3^{}$3) ——对于稠密图效果好

Floyd 算法

• D $k^{}\left[i\right]\left[j\right]$k[i][j] = 路径{ i →{ $l$l ≤ $k$k } → j } 的最小长度
• D $0^{}$0，D $1^{}$1，…，D ${\mid V\mid -1}^{}\left[i\right]\left[j\right]$∣V∣−1[i][j] 即给出了 i 到 j 的真正最短距离
• 最初的 D ${-1}^{}$−1 是全 0 的邻接矩阵
• 若 i 和 j 不直接相连，初始化为无穷大
• 当 D ${k-1}^{}$k−1 已经完成，递推到 D $k^{}$k 时：
  • 或者 $k$k 不属于 最短路径 { i →{ $l$l ≤ $k$k } → j }，则 D $k^{}$k = D ${k+1}^{}$k+1
  • 或者 $k$k 属于最短路径 { i →{ $l$l ≤ $k$k } → j }，则该路径必定由两段最短路径组成：D $k^{}\left[i\right]\left[j\right]$k[i][j] = D ${k-1}^{}\left[i\right]\left[k\right]$k−1[i][k] + D ${k-1}^{}\left[k\right]\left[j\right]$k−1[k][j]

void Floyd(){
    for( i = 0; i < N; i++ )
        for( j = 0; j < N; j++ ){
            D[i][j] = G[i][j];
            path[i][j] = -1;
        }
    for( k = 0; k < N; k++ )
        for( i = 0; i< N; i++)
            for( j = 0; j < N; j++ )
            	if( D[i][k] + D[k][j] < D[i][j] ) {
            		D[i][j] = D[i][k] + D[k][j];
                    path[i][j] = k;
                }
}

#include<iostream>
#include<stdlib.h>
#define INF 1000000
#define MaxVertex 100
typedef int Vertex;
int G[MaxVertex][MaxVertex];
int dist[MaxVertex][MaxVertex];  // 距离 
int path[MaxVertex][MaxVertex];  // 路径 
int Nv;   // 顶点 
int Ne;   // 边 
using namespace std;

// 初始化图信息 
void build(){
	Vertex v1,v2;
	int w;
	cin>>Nv;
	// 初始化图 
	for(int i=1;i<=Nv;i++)
		for(int j=1;j<=Nv;j++)
			G[i][j] = INF;
	cin>>Ne;
	// 初始化点
	for(int i=0;i<Ne;i++){
		cin>>v1>>v2>>w;
		G[v1][v2] = w;  
		G[v2][v1] = w;
	}
}

void Floyd(){
	for(Vertex i=1;i<=Nv;i++)
		for(Vertex j=1;j<=Nv;j++){
			dist[i][j] = G[i][j];
			path[i][j] = -1;
		}
	for(Vertex k=1;k<=Nv;k++)
		for(Vertex i=1;i<=Nv;i++)
			for(Vertex j=1;j<=Nv;j++)
				if(dist[i][k] + dist[k][j] < dist[i][j]){
					dist[i][j] = dist[i][k] + dist[k][j];
					path[i][j] = k;
				}
} 

void output(){
	for(Vertex i=1;i<=Nv;i++){ 
		for(Vertex j=1;j<=Nv;j++)
			cout<<dist[i][j]<<" ";	
		cout<<endl;
	}
	cout<<endl;
	for(Vertex i=1;i<=Nv;i++){ 
		for(Vertex j=1;j<=Nv;j++)
			cout<<path[i][j]<<" ";	
		cout<<endl;
	}
}


int main(){
	build();
	Floyd();
	output();
	return 0;
}