# 最短路徑演算法

## All-Pairs Shortest Path

### Floyd-Warshall algorithm
不可用於有負邊的圖

1. 初始化

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i==j) dis[i][j]=0;  //把自己到自己設成0
        else dis[i][j]=inf;  //把所有點之間設成無限大
    }
}

//輸入時要注意取最小值
for(int i=0,u,v,w;i<m;i++){
    cin >> u >> v >> w;
    if(w<dis[u][v]){
        dis[u][v]=w;
        dis[v][u]=w;
    }
}

可以簡化成在宣告的時候就初始為無限大

vector<vector<int>> Map(n,vector<int>(n,INT_MAX));

for(int i=0;i<n;i++) Map[i][i]=0;

2. 利用dp動態規劃,對於每個點可以是直接抵達(i->j),或者經過地圖上任意一個點(k)抵達(i->k->j),兩者取最小值即為兩個點間的最小距離

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

三層迴圈窮舉i j k
注意:中繼站k要在最外層

for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            Map[i][j]=min(Map[i][j],Map[i][k]+Map[k][j]);
        }
    }
}

這樣就能得到任兩個點(i,j)之間的最短距離

## Single-source Shortest Path

### Dijkstra Algorithm(邊權非負)
可用於有向圖與無向圖,但邊權不能是負的

用於求單點對多點的最短距離,有點像最小生成樹的prim演算法

1. 在還未被設為確定值的元素中找距離起點的最小值
2. 將找到的節點設為確定值,因為不管怎麼繞路都不會有更小的值了
3. 更新此點可走到的其他點

int Dijkstra (int s,int e){
    vector<int> dis(n,1e9);
    dis[s]=0;
    
    vector<bool> confirm(n,false);
    confirm[s]=true;
    
    for(int i=0;i<n;i++){  //反覆尋找與起點最短距離的點,最多n個
        int cur=-1;
        for(int j=0;j<n;j++){
            if(!confirm[j]){  //僅找未被更新的元素
                if(cur==-1 || dis[j]<dis[cur]){  //找最小值
                    cur=j;
                }
            }
        }
        if(cur==-1){
            break;  //此圖剩下的節點走不到
        }
        confirm[cur]=true;  //設為確定值
        for(auto j:Map[cur]){  //更新此節點可走的到的節點的離起點最小值
            int d=value[cur][j];
            if(!confirm[j]){  //僅更新未被確定的元素
                if(dis[cur]+d<dis[j]){  //更新最小值
                    dis[j]=dis[cur]+d;
                }
            }
        }
    }
    if(dis[e]==1e9) cout << "Impossible to reach";
    else cout << dis[e];
}

與prim不同的地方在於最後更新的d的地方,Dijkstra要更新起點到j的距離,prim則是更新最小生成數到j的距離

prim:
判斷有沒有在最小生成樹裡的集合

//d=從最小生成樹到j的最小距離
for(int j=0;j<n;j++){
    if(!visit[j] && map[index][j]<d[j]){
        d[j]=map[index][j];
    }
}

Dijkstra:
算路徑長

//d=從key_poinr到j的最小距離
for(int j=1;j<=n;j++){
    if(map[index][j]!=1e9 && d[index]+map[index][j]>d[j]){  
        d[j]=map[index][j]+d[index];
    }
}

#### priority_queue
在求最小距離時可用priority queue優化

#define pii pair<int,int>
#define val first
#define idx second
//Map[x].push_back({value,y});
//從x走到y權重為value

priority_queue<pii,vector<pii>,greater<pii>> pq;
//以距離排序所以first要放起點到該節點的距離,second才放編號
pq.push({0,s});

vector<int> dis(n,1e9);
dis[s]=0;

while(!pq.empty()){
    pii cur=pq.top();
    pq.pop();
    if(dis[cur.idx]<cur.val) continue;
    //如果到當前節點的value比dis[當前節點]大
    //代表有其他邊可以以更小的value走到到此節點
    //那此節點因為比較大就不更新
    for(auto i:Map[cur.idx]){
        if(dis[cur.idx]+i.val<dis[i.idx]){
            //更新到i.first的最小值
            dis[i.idx]=dis[cur.idx]+i.val;
            pq.push({dis[i.idx],i.idx});
        }            
    }
}

set寫法+二維陣列

//ZJ d793 路徑最小權重和
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int a[MAXN][MAXN];
int dis[MAXN][MAXN];
bool used[MAXN][MAXN];

struct node{
    int val,x,y;
};
bool operator<(const node a,const node b){  //運算子重載,給set排序function
    return a.val<b.val;
}

multiset<node> pq;  
//注意:要multiset,因為在過程中有可能有到此點的更小距離出現但如果用set就會
pq.insert({a[0][0],0,0});
dis[0][0]=a[0][0];

while(!pq.empty()){
    node now=*pq.begin();
    pq.erase(pq.begin());
    
    if(now.val>dis[now.x][now.y]) continue;
    for(int i=0;i<4;i++){
        int tx=now.x+dx[i],ty=now.y+dy[i];
        if(tx>=n || tx<0 || ty>=m || ty<0) continue;
        
        if(now.val+a[tx][ty]<dis[tx][ty]){
            dis[tx][ty]=now.val+a[tx][ty];
            pq.insert({dis[tx][ty],tx,ty});
        }
    }
}
cout << dis[n-1][m-1] << '\n';

### Bellman-Form

也是求單源最短路徑,但可用於負邊,進而判斷是否有負環

枚舉每條邊(from a to b,權重:v),如果從a經過這條邊走到b會小於原其他路走到b,那就更新distance[b]=distance[a]+v;
概念是DP,轉移式如下

dp[k][b]=min(dp[k][b],dp[k-1][a]+value[a][b]);

dp[k][i]代表從起點走k條邊的情況下,走到i的最短距離

1. 最短距離一定是<=n-1條邊,如果>n-1的話就代表有負環,因為只要能再多接一條邊就是繞回去先前已算過的點,這樣就會形成無止盡的負環
2. 最多算n-1次,由小到大,dp轉移式可省略k,因為每次都是執行完k-1後才會到k

綜合以上兩點可以先寫出一份Code

struct node{int a,b,c;};

vector<node> Map;  //紀錄路 from a to b ,權重:c
vector<int> dis(n,1e9);  //紀錄起點到index的最短距離
dis[0]=0;  //初始化設起點到起點為0

for(int v=0;v<n-1;v++){
    //最短距離最多有n-1條邊
    for(auto i:Map){
        //枚舉每一條邊
        if(dis[i.a]+i.v<dis[i.b]){
            //如果從i這條邊到結點b會比其他邊到b小的話
            dis[i.b]=dis[i.a]+i.v;
        }
    }
}

再執行一次即可判斷有無負環,最外層的迴圈也不用了

bool negative_circle=false;
for(auto i:Map){
    if(dis[i.a]+i.v<dis[i.b]){
        negative_circle=true;
        break;
    }
}

### SPFA
全名shortest path faster algorithm
有兩個優點
1. Dijkstra演算法的優化:
在進入queue時先判斷此點是否已在queue裡,如果沒有的話才加入,可省掉相同元素,在出隊後的判斷。入隊的時候,檢查此元素的dis是否小於當前queue的頭的dis,基於greedy,如果有就插入隊伍最前面,否則插入最後面
2. 可判斷負環:
當一個點進入queue的次數>=n(節點數)時,代表被更新了n次,即有負環,因為如果沒有負環的話,經過此點的次數最多只會是n-1(扣除自己的其他節點),不可能再更小,除非有負環

vector<int> dis(n,inf),cnt(n,0);
vector<bool> inq(n,false);  //紀錄此元素是否在queue裡
list<int> q{start};

inq[start]=true;  //紀錄進入queue裡
dis[start]=0;

while(!q.empty()){
    int now=q.front();q.pop_front();
    inq[now]=false;  //紀錄移出queue

    for(auto i:Map[now]){
        if(dis[now]+i.S<dis[i.F]){
            dis[i.F]=dis[now]+i.S;
            if(!inq[i.F]){  //如果沒有在queue裡才加入
                cnt[i.F]++;
                if(cnt[i.F]==n) cout << "negative circle" << '\n';  //有負環
        
                if(!q.empty() && dis[i.F]<dis[q.front()]) q.push_front(i.F);  //如果比前面小就加入前面
                else q.push_back(i.F);  //否則加入後面
                inq[i.F]=true;  //紀錄進入queue
            }
        }
    }
}

### 拓譜排序(DAG)
可同時求最大和最小路徑

利用拓譜排序性質=>走到此點的點都被走過才會走此點
進而更新此點的最短距離

dis[v]=min(dis[v],dis[u]+val(u,v))

for(int i=0;i<n;i++) dis[0][i]=1e9;
    for(int i=0;i<n;i++) dis[1][i]=-1e9;
    
    dis[0][s]=0;
    dis[1][s]=0;

    queue<int> q;
    for(int i=0;i<n;i++) if(task[i]==0) q.push(i);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(auto j:Map[now]){
            int i=j.first;
            dis[0][i]=min(dis[0][i],dis[0][now]+j.second);
            dis[1][i]=max(dis[1][i],dis[1][now]+j.second);
            task[i]--;
            if(task[i]==0){
                q.push(i);
            }
        }
    }

### 求有向圖的且有負邊的最短路徑
如果是無向圖可利用Bellman-Form，因為一個連通圖可以隨意走，只要有負環就可以一直走負環，但有向圖就不一定有一條路徑是通往負環的，所以要檢查負環是否在起點到終點的路徑上，可利用正反兩次dfs求得起點到終點的路徑，再檢查負環是否在路徑上

void dfs(int now,int idx){
	vis[idx][now]=true;
	for(auto i:Map[idx][now]){
		if(!vis[idx][i]) dfs(i,idx);
	}
}

//find the path through starting point and end point,which is vis[0][i] && vis[1][i]
dfs(1,0),dfs(n,1);
	
vector<int> dis(n+1,inf);
dis[1]=0;

//Bellman-Form
for(int i=0;i<n-1;i++){
    for(auto [a,b,c]:road){
        if(dis[a]+c<dis[b]) dis[b]=dis[a]+c;
    }
}
//check whether the negative edge is connected to the path which is through starting point and end point
for(auto [a,b,c]:road){
    if(dis[a]+c<dis[b] && vis[0][b] && vis[1][b]){
        cout << -inf << '\n';
        return;
    }
}
cout << dis[n] << '\n';

UVA 558 (Bellman-Form)

#include <bits/stdc++.h>
using namespace std;

struct edge{int a,b,d;};

bool bellman_ford(vector<edge> &Map,int n){
    vector<int> dis(n,1e9);
    dis[0]=0;

    for(int v=0;v<n-1;v++){
        for(auto i:Map){
            if(dis[i.a]+i.d<dis[i.b]){
                dis[i.b]=dis[i.a]+i.d;
            }
        }
    }
    
    for(auto i:Map){
        if(dis[i.a]+i.d<dis[i.b]){
            return true;
        }
    }
    
    return false;
}


int main(){
    cin.sync_with_stdio(0),cin.tie(0);

    int n,m,t,x,y,d;
    cin >> t;
    while(t--){
        cin >> n >> m;

        vector<edge> Map;
        for(int i=0;i<m;i++){
            cin >> x >> y >> d;
            Map.push_back({x,y,d});
        }
        
        if(bellman_ford(Map,n)) cout << "possible\n";
        else cout << "not possible\n";
    }
}