最短路径算法

最短路问题是什么

最短路问题是指：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值 之和最小的路径。

解决最短路的问题的算法有：

• Bellman_Ford算法

• Dijkstra算法

• Floyed算法

• SPFA算法

---

Bellman_Ford算法

原理

• 松弛

  每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短**。

• 负权值判定

  图的最大深度为​，如果第​次循环中仍有节点的最短距离发生代表，说明有父权值环

• 循环的提前跳出

  在某次循环不再进行松弛时，直接退出循环。

过程

• 初始化

  原点的距离初始化为0，其他点的距离初始化为INF

• 循环

  1. 每次循环遍历所有边，进行松弛操作，如果满足

     则需要进行松弛操作。

  2. 每次循环完之后判断是否有节点的距离更新，如果没有提前退出循环。

  3. 在第​次循环之后判断是否有节点的距离更新，如果有，说明负权值环。

优点和缺点

• 优点

  • 实现简单

  • 可以处理权值为负的图

• 缺点

  • 时间复杂度高

代码

bool Bellman_Ford(int s){
    for(int i = 0; i < vNum; i++) d[i] = INF;//初始化
    d[s] = 0;
    int cnt = 1;//记录循环的次数
    while(true){
        bool update = false;
        for(int i = 0; i < eNum; i++){
            struct Edge e = edges[i];
            if((d[e.from] != INF) && (d[e.to] > d[e.from] + e.w)){
                update = true;
                d[e.to] = d[e.from] + e.w;
            }
        }
        if(!update) break;//没有节点的最短距离改变，提前退出循环
        ++cnt;
        if(cnt == vNum + 1) return false;//如果第|V|次循环仍有节点的最短距离改变，说明有负权值环
    }
    return true;
}

---

Dijkstra算法

Dijkstra算法的引出

考虑没有负权值边的情况。在Bellman_Ford算法中，如果d[i]还不是最短距离的话，即使进行​的更新，d[j]也不会变成最短距离。可以对算法做如下修改：

• 找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离

• 此后不需要更新I中的“最短距离已经确定的顶点

算法过程

• 初始化

  原点的距离初始化为0，其他点的距离初始化为INF

• 循环

  执行以下循环过程，知道所有节点的最小距离都求出

  1. 从未被确认求出最小距离的节点中选出距离最小的节点

  2. 将选出的节点标记为已访求出最小距离

  3. 更新选出的节点的邻居节点的距离

用邻接矩阵表示图

需要维护的数据结构有：

• g[MAX_V][MAX_V]，g[i][j]=w表示从i指向j的边的权值为w(w=-1时表示没有从i指向j的边)

• visited[MAX_V]，visited[i]=1表示节点i的最小距离已经确认

• d[MAX_V]，d[i]表示节点i的最小距离

取出最小距离的点时，遍历d数组，找出为最小距离未被确认的节点中，距离最小的点

更新邻居节点的距离时，遍历g[v]数组，更新v的邻居节点的距离

void Dijkstra(){
    for(int i = 0; i < vNum; i++) d[i] = INF;
    d[0] = 0;
    while(true){
        int v = -1;//seleted node with min d
        //choose the node whose d is minimal
        for(int i = 0; i < vNum; i++){
            if(!visited[i] && (v == -1 || d[i] < d[v])) v = i;
        }
        
        //all nodes have been included
        if(v == -1) break;
        visited[v] = 1;
        //update d of the v'neighbors
        for(int i = 0; i < vNum; i++){
            if(g[v][i] != -1 && (d[i] > d[v] + g[v][i])){
                d[i] = d[v] + g[v][i];
            }
        }
    }
    print();
}

---

用邻接链表表示图

需要维护的数据结构有：

• vector<p> g[MAX_V]，g[i]的类型是vector<p>，g[i]表示节点i的邻居节点

• visited[MAX_V]，visited[i]=1表示节点i的最小距离已经确认

• d[MAX_V]，d[i]表示节点i的最小距离

取出最小距离的点时，遍历d数组，找出为最小距离未被确认的节点中，距离最小的点

更新邻居节点的距离时，遍历gv，更新v的邻居节点的距离

void Dijkstra()
{
    for(int i = 0; i < vNum; i++)
    {
        d[i] = INF;
    }
    d[0] = 0;
    while(true)
    {
        int u = -1;
        for(int i = 0; i < vNum; i++)
        {
            if(!visited[i] && (u == -1 || d[i] < d[u])) u = i;
        }
        if(u == -1) break;
        visited[u] = 1;

        vector<p>::iterator it;
        for(it = g[u].begin(); it != g[u].end(); it++)
        {
            int v = (*it).first;
            int w = (*it).second;
            if(!visited[v] && (d[v] > d[u] + w))
            {
                d[v] = d[u] + w;
            }
        }
    }
}

---

用链式向前星表示图

用链式向前星表示图，用优先级队列取出最小距离的节点

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> p; 

const int INF = 10000;
const int MAX_V = 100;
const int MAX_E = 10000;

struct Edge{
    int to;
    int w;
    int next;
};
//user defined comparer
struct mycmp{
    bool operator()(p p1, p p2){
        return p1.second > p2.second;
    }
};

struct Edge edge[MAX_E];
int head[MAX_V];
int cnt;

int d[MAX_V];
int visited[MAX_V];
int vNum;
int eNum;

void addEdge(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void print(){
    for(int i = 0; i < vNum; i++){
        printf("%d d:%d\n", i, d[i]);
    }
}

void Dijkstra(){
    priority_queue<p, vector<p>, mycmp> q;//notice
    for(int i = 0; i < vNum; i++){
        d[i] = INF;
    }
    d[0] = 0;
    q.push(make_pair(0, 0));
    while(!q.empty()){
        int u = q.top().first; q.pop();
        printf("pop:%d d:%d\n", u, d[u]);
        visited[u] = 1;
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            int w = edge[i].w;
            if(!visited[v] && (d[v] > d[u] + w)){
                d[v] = d[u] + w;
                q.push(make_pair(v, d[v]));
                printf("push:%d d:%d\n", v, d[v]);
            }
        }
    }
}

int main(){
    memset(visited, 0, sizeof(visited));
    memset(head, -1, sizeof(head));
    cnt = 0;
    scanf("%d %d", &vNum, &eNum);
    for(int i = 0; i < eNum; i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);   
    }
    Dijkstra();
    //print();
    return 0;
}