单源最短路径、所有结点对的最短路径

算法核心:两个结点之间的一条最短路径包含着(包含于)其它的最短路径.[最短路径性质]

1.单源最短路径Dijkstra

思路:计算每个结点到源结点的距离,压入最小优先队列Q,对Q中的元素进行如下循环操作:

1.从队列Q中弹出最小元素u
2.将u并入S
3.对u的邻接表中每个结点v,调用Relax(u,v,w)更新结点v到源结点s的距离

直至Q为空.

伪代码:

Initialize-Single-Source(G,s)
    for each vertex v in G.v
        v.d = MAX
        v.p = NIL
    s.d = 0
Realx(u,v,w)
    if v.d > u.d + w[u][v]
        v.d = u.d + w[u][v]
        v.p = u
Dijkstra(G,w,s)
    Initialize-Single-Source(G,s)
    S = ∅//已经找到到源结点s的最短路径的结点的集合
    Q = G.V//Q是以结点到源结点距离为priority的最小优先队列
    while Q ≠ ∅
        u = EXTRACT-MIN(Q)
        S = S∪{u}
        for each vertex v in G.Adj[u]
            Relax(u,v,w)

时间复杂度:O(|V|2)

编码实现:

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
#include<set>
#include<cassert>
using namespace std;
#define MAX 10000
enum Color{white,gray,black};

class Node{
public:
    int index;
    Node* next=nullptr;//
    Node(int i):index(i){}
};
class VNode{
public:
    char vertex;
    int index;
    int dist;
    int final;
    int indegree;
    Color color=white;
    int prev=-1;
    Node* firstNode=nullptr;
    VNode(char c,int i):vertex(c),index(i){}
};
typedef struct Graph{
    int EdgeNum;
    vector<VNode> Adj;
}Graph;
void initialize_single_source(Graph &G,int s,int w[][6]){
    for(auto &v:G.Adj){//use reference**************
        v.dist = MAX;//w[0][v.index];
        v.prev = -1;
    }
    G.Adj[s].dist = 0;
}
void relax(Graph &G,int u,int v,int w[][6]){
    if(G.Adj[v].dist > G.Adj[u].dist + w[u][v]){
        G.Adj[v].dist = G.Adj[u].dist + w[u][v];
        G.Adj[v].prev = u;
    }
}
//为优先队列提供比较结构,小的优先
struct comp
{
    bool operator () (VNode &a,VNode &b)const{
        return a.dist>b.dist;
    }
};
void dijkstra(Graph &G,int w[][6],int s){
    initialize_single_source(G,s,w);
    set<int> S;
    priority_queue<VNode,vector<VNode>,comp> Q;
    for(int i=0;i<G.Adj.size();i++){
        Q.push(G.Adj[i]);
    }
    while(!Q.empty()){
        int u = (Q.top()).index;
        Q.pop();
        S.insert(u);
        Node* p = G.Adj[u].firstNode;
        while(p != nullptr){
            int v = p->index;
            relax(G,u,v,w);
            p = p->next;
        }
        //由于保存在Q中的元素是结点的副本,故结点到源结点距离改变时,优先队列Q不会受到影响,也就是Q不会像我们期望的那样工作,故需重新生成Q
        priority_queue<VNode,vector<VNode>,comp> Q3;
        while(!Q.empty()){
            VNode vn=Q.top();
            Q.pop();
            Q3.push(G.Adj[vn.index]);
        }
        Q=Q3;
    }
}
void AddEdge(Graph &G,int i,int j){
    Node* p = new Node(j);
    p->next = G.Adj[i].firstNode;
    G.Adj[i].firstNode = p;
}

void print_path(Graph &G,int s,int v){
    if(v == s){
        cout<<G.Adj[s].vertex<<",";
    }
    else if(G.Adj[v].prev  == -1){
        cout<<"No such path!";
    }
    else{
        print_path(G, s, G.Adj[v].prev);
        cout<<G.Adj[v].vertex<<",";
    }
}

int main(){
    Graph G;
    G.EdgeNum = 8;
    vector<char> v={'a','b','c','d','e','f'};
    for(int i=0;i<v.size();i++){
        G.Adj.push_back(VNode(v[i], i));
    }
    AddEdge(G,0,2);
    AddEdge(G,0,4);
    AddEdge(G,0,5);
    AddEdge(G,1,2);
    AddEdge(G,2,3);
    AddEdge(G,3,5);
    AddEdge(G,4,3);
    AddEdge(G,4,5);
    int w[6][6];
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
                        if(i==j){
                            w[i][j] = 0;
                         }
                         else{
                w[i][j] = MAX;
                         }
        }
    }
    w[0][2] = 10;
    w[0][4] = 30;
    w[0][5] = 100;
    w[1][2] = 5;
    w[2][3] = 50;
    w[3][5] = 10;
    w[4][3] = 20;
    w[4][5] = 60;
    dijkstra(G,w,0);
    for(int i=1;i<G.Adj.size();i++){
        cout<<G.Adj[i].dist<<'	';
        print_path(G,0,i);
        cout<<endl;    
    }
    return 0;
}
View Code

2.所有结点对的最短路径FloydWarshall

思路:对每对结点[i,j],尝试向中间加入结点k,如果w[i][j] > w[i][k] + w[k][j],则更新[i,j]之间的最短距离为w[i][j] = w[i][k] + w[k][j].由于k的加入使w[i][j]变小,故k属于结点对[i,j]的最短路径上的点,另外,由于最短路径性质,[i,j]的最短路径由[i,k]和[k,j]的最短l路径组成.

伪代码:

void FloydWarshall(Graph &G,int w[][6],int v[][6]){
    for(int k=0;k<6;k++){
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                if(w[i][j]>w[i][k]+w[k][j]){
                    w[i][j] = w[i][k]+w[k][j];
                    v[i][j] = k;//记下[i,j]的最短路径的中间结点        
                }
            }
        }
    }
}

时间复杂度:O(|V|3)

编码实现:

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
#include<set>
#include<cassert>
using namespace std;
#define MAX 10000
enum Color{white,gray,black};
class Node{
public:
    int index;
    Node* next=nullptr;//
    Node(int i):index(i){}
};
class VNode{
public:
    char vertex;
    int index;
    int dist;
    int final;
    int indegree;
    Color color=white;
    int prev=-1;
    Node* firstNode=nullptr;
    VNode(char c,int i):vertex(c),index(i){}
};
typedef struct Graph{
    int EdgeNum;
    vector<VNode> Adj;
}Graph;
void FloydWarshall(Graph &G,int w[][6],int v[][6]){
    for(int k=0;k<6;k++){
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                if(w[i][j]>w[i][k]+w[k][j]){
                    w[i][j] = w[i][k]+w[k][j];
                    v[i][j] = k;                
                }
            }
        }
    }
}
void AddEdge(Graph &G,int i,int j){
    Node* p = new Node(j);
    p->next = G.Adj[i].firstNode;
    G.Adj[i].firstNode = p;
}
void print_path(const Graph &G,int i,int j,const int v[][6]){
    if(v[i][j]==-1){
        cout<<G.Adj[i].vertex<<',';
    }
    else{
        print_path(G,i,v[i][j],v);
        print_path(G,v[i][j],j,v);
    }
}
int main(){
    Graph G;
    G.EdgeNum = 8;
    vector<char> v={'a','b','c','d','e','f'};
    for(int i=0;i<v.size();i++){
        G.Adj.push_back(VNode(v[i], i));
    }
    AddEdge(G,0,2);
    AddEdge(G,0,4);
    AddEdge(G,0,5);
    AddEdge(G,1,2);
    AddEdge(G,2,3);
    AddEdge(G,3,5);
    AddEdge(G,4,3);
    AddEdge(G,4,5);
    int w[6][6];
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            if(i==j){
                w[i][j]=0;
            }
            else{
                w[i][j] = MAX;                
            }
        }
    }
    w[0][2] = 10;
    w[0][4] = 30;
    w[0][5] = 100;
    w[1][2] = 5;
    w[2][3] = 50;
    w[3][5] = 10;
    w[4][3] = 20;
    w[4][5] = 60;
    int path[6][6];
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            path[i][j]=-1;
        }
    }
    FloydWarshall(G,w,path);
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            if(w[i][j]!=MAX && i!=j){
                cout<<'['<<i<<','<<j<<']'<<'	';
                cout<<w[i][j]<<'	';
                print_path(G,i,j,path);
                cout<<G.Adj[j].vertex<<',';
                cout<<endl;
            }    
        }
    }
    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/bukekangli/p/4394707.html