最短路徑演算法

提出者

• 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;
}

提出者

• 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;
}

提出者

• 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;
}