# 最短路徑演算法

---

## 問題敘述
* 給定一個帶權圖G，求一條路徑讓S到T的權重總和最小。
* 有兩種題型
* 全點對
* 單點源

---

## Floyd Warshall

* 全點對最短路徑演算法
* 好寫
* 動態規劃

----

## 提出者

* Robert W．Floyd
* 不是理科專業而是文組
* 以heapsort獲得1980年的圖靈獎

----

## 鬆弛(Relax)

$dist[s][t]=min(dist[s][t],dist[s][k]+dist[k][t])$

----

## DP

* 設dp[i][j][k]為從i到j使用前k個點進行鬆弛後的最短路徑
* 如果k鬆弛可以更短$dp[i][j][k]=dp[i][k][k-1]+dp[k][j][k-1]$
* 如果無法更短$dp[i][j][k]=dp[i][j][k-1]$
* $dp[s][t]=min(dp[s][t],dp[s][k]+dp[k][t])$

----

## 時間複雜度

$O(n^3)$

----

## code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mp[1005][1005];
void floyd_wharshall(int n){
    for(int k=0;k<n;++k)
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
int main(){
    memset(mp,0x3f,sizeof(mp));
    int n,m;cin>>n>>m;
    for(int i=0;i<m;++i){
        int a,b,w;
        cin>>a>>b>>w;
        mp[a][b]=w;mp[b][a]=w;
    }
    for(int i=0;i<n;++i)mp[i][i]=0;
    floyd_wharshall(n);
    return 0;
}

---

## Bellman Ford

* 單點對最短路
* 支持負邊權
* 可尋找負環

----

## 提出者

* Richard Bellman 和 Lester Randolph Ford Jr. 以及 Edward F. Moore
* Richard Bellman :動態規劃的創始人
* Lester Randolph Ford Jr. :
確立了最大流量最小割定理
* Edward F. Moore :人工智慧先驅

----

## 鬆弛(Relax)

* 設dist[t]為u到t的最短路
* $dist[t]=min(dist[t],dist[v]+len[v][t])$

----

## 過程

* 每條邊都試一遍，一定能找到一條邊進行鬆弛
* 如果無法鬆弛，演算法便停止
* 如果每條邊都鬆弛過卻還能鬆弛->有負環

----

## 時間複雜度

$O(n^2)$

----

struct data{
    int a,b,w;
}edge[100005];
ll dist[100005];
void bellman_ford(int n,int m){
    memset(dist,0x3f,sizeof(dist));
    for(int i=0;i<n;++i){
        bool valid=0;
        for(int j=0;j<m ;++j){
            if(dist[edge[j].a]>dist[edge[j].b]+edge[j].w){
                dist[edge[j].a]=dist[edge[j].b]+edge[j].w;
                valid=1;
            }
            if(dist[edge[j].b]>dist[edge[j].a]+edge[j].w){
                dist[edge[j].b]=dist[edge[j].a]+edge[j].w;
                valid=1;
            }
        }
        if(!valid)return;
        if(i==n-1){
            cout<<"negative\n";
            return;
        }
    }
}

----

## code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct data{
    int a,b,w;
}edge[100005];
ll dist[100005];
void bellman_ford(int n,int m){
    memset(dist,0x3f,sizeof(dist));
    for(int i=0;i<n;++i){
        bool valid=0;
        for(int j=0;j<m ;++j){
            if(dist[edge[j].a]>dist[edge[j].b]+edge[j].w){
                dist[edge[j].a]=dist[edge[j].b]+edge[j].w;
                valid=1;
            }
            if(dist[edge[j].b]>dist[edge[j].a]+edge[j].w){
                dist[edge[j].b]=dist[edge[j].a]+edge[j].w;
                valid=1;
            }
        }
        if(!valid)return;
        if(i==n-1){
            cout<<"negative\n";
            return;
        }
    }
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>edge[i].a>>edge[i].b>>edge[i].w;
    }
    bellman_ford(n,m);
    return 0;
}

---

## Dijkstra

* 單點對最短路
* 不支持負邊權
* 最快的演算法

----

## 提出者

* Edsger Wybe Dijkstra
* 荷蘭人
* 以結構化編程和程式語言科學化獲得1972年圖靈獎
* 和演算法之父Donald Ervin Knuth並稱這世代最偉大的電腦科學家

----

## 過程

* 設置一集合S代表走過的點
* 找到一條權重最小的邊連結集合中的一點和未在集合中的一點
* 重複執行直到所有點都走過

----

## 時間複雜度

$O(n^2)$

----

## 優化

* 使用heap找最小權重之邊
* $O(n^2)->O(nlogn)$

----

#define ll long long
#define ff first
#define ss second
#define mp make_pair
vector<pair<int,ll>> v[100005];
ll dist[100005];
void dijkstra(int u){
    memset(dist,0x3f,sizeof(dist));
    priority_queue<pair<ll,int> > pq;
    pq.emplace(0,u);
    while(!pq.empty()){
        auto tmp=pq.top();pq.pop();
        if(dist[tmp.ss]!=0x3f3f3f3f3f3f3f3f)continue;
        dist[tmp.ss]=-tmp.ff;
        for(auto e:v[tmp.ss])
            pq.emplace(-(e.ss-tmp.ff),e.ff);
    }
}

----

## code

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define mp make_pair
using namespace std;
vector<pair<int,ll>> v[100005];//存圖
ll dist[100005];//存原點到各點的最短路
void dijkstra(int u){
    memset(dist,0x3f,sizeof(dist));//初始化
    priority_queue<pair<ll,int> > pq;
    pq.emplace(0,u);
    while(!pq.empty()){//重複執行直到所有點都走過
        auto tmp=pq.top();pq.pop();
        if(dist[tmp.ss]!=0x3f3f3f3f3f3f3f3f)continue;
        dist[tmp.ss]=-tmp.ff;
        for(auto e:v[tmp.ss])
            pq.emplace(-(e.ss-tmp.ff),e.ff);
    }
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=0;i<m;++i){
        int a,b,w;
        cin>>a>>b>>w;
        v[a].emplace_back(mp(b,w));
        v[b].emplace_back(mp(a,w));
    }
    int s,t;//尋找s~t的最短路
    cin>>s>>t;
    dijkstra(s);
    cout<<dist[t]<<'\n';
    return 0;
}

---