---
title: 最短路徑
tags: 7th 教學
slideOptions:
theme: black
transition: 'slide'
---
<style type="text/css">
.slides {
text-align: left !important;
}
</style>
# 最短路徑

## 為甚麼需要最短路徑

## 要怎麼找到最短路徑?
以下有三種演算法 各有各自的優缺點 需要靠自己多寫題目用心體會

### floyd warshall全點對最短路徑
想法非常的直覺
我們枚舉一個$k$當作中繼站
再枚舉一對$(i,j)$當作起訖點
那我們得到一個轉移式
$dp[i][j]=\min\limits_{1\le k\le n}(dp[i][j],dp[i][k]+dp[k][j]);$
我們就可以得到任意點對$(i,j)$的距離了
[例](https://tioj.ck.tp.edu.tw/problems/1096)
複雜度:$O(V^3)$
:::success
可以得到全點對的距離
:::
:::danger
慢到靠北 很少用到
:::
### Dijkstra單源最短路徑演算法
概念上有點像BFS 我們用priority_queue來取代BFS裡面的queue
這次我們是優先對清單中離源頭最近的點遍歷
而決定我們要不要遍歷下去的因素也不再是訪問過與否
而是我們從這邊走下去是否比原先的走法還划算
複雜度:$O(E\log V)$
範例代碼:

#define pii pair<int,int>
vector<pii>path[N];
int dis[N];
std::priority_queue<pii,vector<pii>,greater<pii>>pq;
void solve()
{
    pq.push({0,s});
    for(int i=0;i<=n;i++)dis[i]=1e9;
    dis[s]=0;
    while(pq.size())
    {
        int now=pq.top().S;
        pq.pop();
        if(dis[now]!=INF)continue;
        for(auto[i,val]:path[now])
        {
            pq.push({dis[now]+val,i});
        }
    }
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}

:::success
快
:::
:::danger
遇到負邊會爆掉 不能拿來寫MCMF :cry:
:::
### Bellman-Ford單源路徑演算法
我們使用一個queue來做為我們的清單
每次抓queue的頭出來做事
也就是對他周圍的點做鬆弛 假設有一點$v$成功鬆弛且不在queue裡面
則把他放進queue裡
就這樣一直做到queue變成空的為止
複雜度:$O(VE)$
範例代碼:

#define pii pair<int,int>
vector<pii>path[N];
int dis[N];
queue<int>q;
bool in_queue[N];
void solve()
{
    q.push(s);
    for(int i=0;i<=n;i++)dis[i]=1e9;
    dis[s]=0;
    in_queue[s]=1;
    while(q.size())
    {
        int now=q.front();
        q.pop();
        for(auto[i,val]:path[now])
        {
            if(dis[i]>dis[now]+val)
            {
                dis[i]=dis[now]+val;
                if(in_queue[i]==0)
                {
                    in_queue[i]=1;
                    q.push(i);
                }
            }
        }
    }
    in_queue[now]=0;
}

:::success
可以負邊~~MCMF~~
:::
:::danger
有可能被題目刻意卡 過不了時限
:::