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

╰半夏微凉° 2022-04-16 04:37 149阅读 0赞

## 最短路径问题 ##

### 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 i\}
 *  对任一未收录的顶点 v，定义 dist\[v\] 为 s 到 v 的最短路径长度，但该路径仅经过 S 中的顶点。即路径 \{s→(v i \_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 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 3 \+ |E|×|V|) ——对于稀疏图效果好
 *  Floyd 算法
    
    T = O(|V| 3 ^3 3) ——对于稠密图效果好

#### Floyd 算法 ####

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