昨天： __ "圖論概念與記錄圖的方法" __ 以上是昨天的Blog，有需要者請先閱讀完以上再閱讀今天的Blog。可能今天的有點亂，好好理理，認真看完相信你會懂得分割線第二天引子：昨天我們~~簡單~~講了講圖的概念與記錄圖的方法，那麼大家有一定的底子了，我們就開始初步接觸圖論演算法了！我們 ...

昨天： 圖論-概念與記錄圖的方法

以上是昨天的Blog，有需要者請先閱讀完以上再閱讀今天的Blog。

可能今天的有點亂，好好理理，認真看完相信你會懂得

分割線

第二天

引子：昨天我們簡單講了講圖的概念與記錄圖的方法，那麼大家有一定的底子了，我們就開始初步接觸圖論演算法了！

我們只講Dijkstra和Floyd，因為其實在比賽中會這兩個演算法就很好了。

今天我們要講的是：最短路徑問題

Top1：最短路的概念

相信大家都知道有一款Made in China的導航軟體——百度導航。那麼他們是怎麼為我們導航的？就是使用了今天我們要學的問題 最短路徑 。

~~說不定你學了之後就可以做一個導航的~~ ~~是不是有點小激動？~~

$\color{red}\text{ 重點：最短路問題就是一個點到另一個最短的路徑！ }$

最短路專業術語：

鬆弛： 既然求一個點到另一個點最短的路徑，那麼肯定就會有更優的路徑替代目前路徑的操作。這就叫做 鬆弛操作。

中轉點： 一個點到另一個點不一定是有直接道路連接的，可能會經過一些別的點，我們就叫那些點叫做 中轉點 。

Top2:Floyd演算法

現在大家都知道最短路是什麼了，那麼從簡單到複雜，我們先來看看新手必懂的演算法。

Floyd簡單粗暴，就是枚舉三個點，一個起點，一個終點，一個中轉點。看 起點到中轉點的路徑 加上 中轉點到終點的路徑 是不是小於 目前起點到終點的路徑 即可（就是不斷鬆弛）。

顯而易見，Floyd演算法很好懂，就是時間複雜度高了點—— $N^3$ 的複雜度。而且，Floyd是多源最短路，詢問時只需調用dis就行了。

所以， 當 N 大於1000時，慎用！

代碼就很簡答啦(蒟蒻用鄰接矩陣寫的)：

//如果為無向圖,dis就會對稱,Floyed的j就只要到i,且dis[i][j]dis[j][i] 要一起更新 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 10;
int n,m;
int x,y,z;
int dis[MAXN][MAXN];
void Floyd(){
    for(int k = 1;k <= n; k++)
        for(int i = 1;i <= n; i++)
            for(int j = 1;j <= n/*i*/; j++)
                if(dis[i][k] + dis[k][j] < dis[i][j])dis[i][j] = dis[i][k] + dis[k][j];
    return;
}
int main(){
    cin>>n>>m;
    for(int i = 1;i <= n; i++)dis[i][i] = 0;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++){
            if(i != j)dis[i][j] = 1e9;
        }
    for(int i = 1;i <= m; i++){
        cin>>x>>y>>z;
        dis[x][y] = z;
    }
    Floyd();
    for(int i = 1;i <= n; i++){
        for(int j = 1;j <= n; j++){
            cout<<dis[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

分割線

Top3：Dijkstra演算法

Dijkstra與Floyd相反，是單元最短路，即只能求出一個點到其他所有點的最短路。

Dijkstra屬於貪心的思想，正解：

首先定義兩個種類——黑點和白點，黑點就是在目前算完最短路徑的點，白點反之。

每次在白點中找一個離目前任意一個黑點最近的，加入黑點，更新白點到原點的最短路即可。

代碼如下：註意：這裡的dis不再是鄰接矩陣，是單源最短路徑。tot才是鄰接矩陣！

鄰接矩陣，蒟蒻是用洛谷P1828 香甜的黃油 Sweet Butter 作為例題寫的模板，體諒一下

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
struct Node{
    int x,y;
}f[MAXN];
int n,m,a,b,s,t;
bool black[MAXN];
double dis[MAXN];
double tot[MAXN][MAXN];
double calc(int i,int j){
    return sqrt((f[i].x - f[j].x) * (f[i].x - f[j].x) + (f[i].y - f[j].y) * (f[i].y - f[j].y));
}
double Dijkstra(int start,int end){
    for(int i = 1;i <= n; i++){
        dis[i] = tot[start][i];
    }
    dis[start] = 0;
    black[start] = true;
    for(int i = 1;i < n; i++){
        double M = 2e9;
        int u = start;
        for(int j = 1;j <= n; j++){
            if(dis[j] < M && !black[j]){
                M = dis[j];
                u = j;
            }
        }
        if(u == start)continue;
        //此處的判斷與前面的u = start對應,若該圖存在一個單獨的點這裡就要加上
        //否則可以u = 0,這個判斷刪掉 
        black[u] = true;
        for(int j = 1;j <= n; j++){
            if(black[j])continue;
            if(dis[u] + tot[u][j] < dis[j]){
                dis[j] = dis[u] + tot[u][j];
            }
        }
    }
    return dis[end];
} 
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++){
            tot[i][j] = i == j ? 0 : 1e9;
        }
    for(int i = 1;i <= n; i++){
        scanf("%d%d",&f[i].x,&f[i].y);
    }
    scanf("%d",&m);
    for(int i = 1;i <= m; i++){
        scanf("%d%d",&a,&b);
        tot[a][b] = calc(a,b);
        tot[b][a] = tot[a][b];
    }
    scanf("%d%d",&s,&t);
    printf("%.2f",Dijkstra(s,t));
    return 0;
}

所以，Dijkstra的時間複雜度是 $N^2$

怎麼優化呢？很簡單——在尋找離黑點最近的白點時，使用優先隊列即可。

優先隊列Dijkstra：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 800 + 10;
const int MAX = 1e9;
int n,m,p,x,y,z;
int a[MAXN];
int dis[MAXN];
int tot[MAXN][MAXN];
vector<int> nei[MAXN];
struct Node{
    int num,dist;
    bool operator < (const Node& next) const {
        return dist > next.dist;
    }
};
void Dijkstra(int start){
    priority_queue <Node> cow;
    for(int i = 1;i <= n; i++){
        dis[i] = 2e9;
    }
    dis[start] = 0;
    Node tt = {start,0};
    cow.push(tt);
    while(!cow.empty()){
        tt = cow.top();
        cow.pop();
        int u = tt.num;
        for(int i = 0;i < nei[u].size(); i++){
            int p = nei[u][i];
            if(dis[u] + tot[u][p] < dis[p]){
                dis[p] = dis[u] + tot[u][p];
                Node next;
                next.num = p;
                next.dist = dis[p];
                cow.push(next);
            }
        }
    }
    return;
} 
int main(){
    scanf("%d%d%d",&n,&m);
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= i; j++){
            tot[i][j] = tot[j][i] = i == j ? 0 : MAX;
        }

    for(int i = 1;i <= m; i++){
        scanf("%d%d%d",&x,&y,&z);
        tot[x][y] = z;
        tot[y][x] = z;
        nei[x].push_back(y);
        nei[y].push_back(x);
    }

    int s,t;
    scanf("%d%d",&s,&t);
    Dijkstra(s);
    cout<<dis[t]<<"\n";
    return 0;
}

順便帶一下SPFA的演算法模板和用動態數組記錄的Dijkatra(這裡不做詳解了，有需要的人可以複製看一下)

SPFA：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring> 
using namespace std;
int n, p, c, cow[801], a, b, d, cnt = 0, sum = 0, ans = 2147483647;
int dis[10000], w[10000], next[10000], to[10000], first[10000] = {0};
bool exist[10000] = {false};
queue<int> q;

void addEdge(int u, int v, int weight)
{
    cnt++; //邊的編號 
    to[cnt] = v; //第cnt條邊指向點v 
    w[cnt] = weight; //第cnt條邊的權值 
    next[cnt] = first[u]; // 第cnt條邊指向連接點u的第一條邊 
    first[u] = cnt; //將連接點u的第一條邊更新為第cnt條邊
    return; 
} 

void spfa(int start)
{
    memset(exist, false, sizeof(exist)); //一開始所有點在隊列外 
    memset(dis, 0x7f, sizeof(dis)); //將所有點到起始點的距離置為極大值 
    dis[start] = 0; 
    q.push(start); //起始點入隊列 
    exist[start] = true; 
    while(!q.empty())
    {
        int head = q.front(); //取隊列的第一個點 
        q.pop();
        exist[head] = false;
        for(int e = first[head]; e != 0; e = next[e]) //迴圈head連接的每一條邊 
        {
            //鬆弛操作 
            if(dis[head] + w[e] < dis[to[e]])
            {
                dis[to[e]] = dis[head] + w[e];
                if(exist[to[e]] == false)
                {
                    q.push(to[e]); //將被更新的點入隊列 
                    exist[to[e]] = true;
                }
            }
        }
    }
    return;
}

int main()
{
    cin >> n >> p >> c;
    for(int i=1; i <= n; i++) //輸入每頭牛所在的位置 
    {
        cin >> cow[i];
    }
    for(int e=1; e <= c; e++) //輸入每一條邊 
    {
        cin >> a >> b >> d;
        addEdge(a, b, d);
        addEdge(b, a, d);
    }
    for(int i=1; i <= p; i++) //註意是迴圈牧場
    {
        spfa(i);
        sum = 0;
        for(int j=1; j <= n; j++)
        {
            sum = sum + dis[cow[j]];
        }
        ans = min(ans, sum);
    }
    cout << ans;
    return 0;
}

動態數組Dijkstra：

#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int n, p, c;
const int INF = 1e9;
int cow[805], dis[805], vertex[805][805];
vector<int> neighbor[805]; 

struct Node
{
    int id, dist;
    bool operator < (const Node & second) const
    {
        return dist > second.dist;
    }
};

void dijkstra(int start)
{
    priority_queue<Node> pq;
    for(int i = 1; i <= p; i++)
    {
        dis[i] = INF;
    }
    dis[start] = 0;
    Node cur = {start, 0}; //起始點和其到dis[start] 
    pq.push(cur);
    while(!pq.empty())
    {
        cur = pq.top();
        pq.pop();
        int u = cur.id;
        for(int i=0; i <= neighbor[u].size() - 1; i++)
        {
            int v = neighbor[u][i]; //與u相鄰的邊v 
            if(dis[u] + vertex[u][v] < dis[v])
            {
                dis[v] = dis[u] + vertex[u][v];
                Node next;
                next.id = v;
                next.dist = dis[v];
                pq.push(next);
            }
        }
    }
    return;
} 

int main()
{
    cin >> n >> p >> c;
    for(int i = 1; i <= n; i++) //輸入每頭牛所在的位置 
    {
        cin >> cow[i];
    }
    for(int i=1; i <= p; i++)
    {
        for(int j=1; j <= p; j++)
        {
            vertex[i][j] = (i == j) ? 0 : INF;
        }
    }
    for(int i=1; i <= c; i++) //輸入每一條邊 
    {
        int a, b, d;
        cin >> a >> b >> d;
        vertex[a][b] = d;
        vertex[b][a] = d;
        neighbor[a].push_back(b);
        neighbor[b].push_back(a); 
    }
    int ans = INF;
    for(int i=1; i <= p; i++) //註意是迴圈牧場
    {
        dijkstra(i); //假如把糖放在第i個牧場 
        int sum = 0;
        for(int j=1; j <= n; j++)
        {
            sum = sum + dis[cow[j]];
        }
        ans = min(ans, sum);
    }
    cout << ans;
    return 0;
}

好了，第二天就到這裡，是不是都聽懂了呢狗屁？歡迎在下方留言！

圖論-最短路徑<Dijkstra,Floyd>

第二天