最短路問題（單源+多源最短路問題）

最短路問題的幾種情況及實作模闆

最短路的常見情況總結及算法

最短路問題（單源+多源最短路問題）

樸素的Dijkstra算法：（注：若所有權重都相等，可以采取BFS寬度優先搜尋來找最短路）

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。

請你求出1号點到n号點的最短距離，如果無法從1号點走到n号點，則輸出-1。

輸入格式

第一行包含整數n和m。

接下來m行每行包含三個整數x，y，z，表示點x和點y之間存在一條有向邊，邊長為z。

輸出格式

輸出一個整數，表示1号點到n号點的最短距離。

如果路徑不存在，則輸出-1。

資料範圍

1≤n≤500,

1≤m≤105,

圖中涉及邊長均不超過10000。

輸入樣例：

3 3

1 2 2

2 3 1

1 3 4

輸出樣例：

算法思想：兩重循環，循環n次，每一次找出路徑最短的點，用它來更新其他點的距離（n個點）

算法如下：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=510;
int m,n;
int g[N][N],dist[N];
bool st[N];

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for (int i=0;i<n;i++){ //循環n次或者n-1次都可以
        int t=-1;
        for (int j=1;j<=n;j++){
            if(!st[j] && (t==-1 ||dist[t]>dist[j])) 
                t=j;
        }
        st[t]=true;
        for (int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}



int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    int t=dijkstra();
    printf("%d\n",t);
    return 0;
    
}

堆優化版的Dijkstra算法

優化點在于找出最短路徑的點，用堆來優化，整體思想基本一樣

代碼如下：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

bellman_ford算法（存在負權變）note：處理最多經過k條邊的最短路徑隻能用此算法

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，邊權可能為負數。

請你求出從1号點到n号點的最多經過k條邊的最短距離，如果無法從1号點走到n号點，輸出impossible。

注意：圖中可能存在負權回路。

輸入格式

第一行包含三個整數n，m，k。

接下來m行，每行包含三個整數x，y，z，表示點x和點y之間存在一條有向邊，邊長為z。

輸出格式

輸出一個整數，表示從1号點到n号點的最多經過k條邊的最短距離。

如果不存在滿足條件的路徑，則輸出“impossible”。

資料範圍

1≤n,k≤500,

1≤m≤10000,

任意邊長的絕對值不超過10000。

輸入樣例：

3 3 1

1 2 1

2 3 1

1 3 3

輸出樣例：

算法思想：循環k次，每次周遊所有邊，更新距離

代碼如下：

//單源最短路問題
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=510,M=10010;

int dist[N],backup[N];
int n,k,m;

struct Edge{
    int a,b,w;
} edges[M];

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for (int i=0;i<k;i++){
        memcpy(backup,dist,sizeof dist);//防止聯通，傳回狀态
        for (int j=0;j<m;j++){
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    else return dist[n];
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    int t=bellman_ford();
    if(t==-1) puts("impossible");
    else printf("%d\n",t);
    
    return 0;
}

spfa算法

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，邊權可能為負數。

請你求出1号點到n号點的最短距離，如果無法從1号點走到n号點，則輸出impossible。

資料保證不存在負權回路。

輸入格式

第一行包含整數n和m。

接下來m行每行包含三個整數x，y，z，表示點x和點y之間存在一條有向邊，邊長為z。

輸出格式

輸出一個整數，表示1号點到n号點的最短距離。

如果路徑不存在，則輸出”impossible”。

資料範圍

1≤n,m≤105,

圖中涉及邊長絕對值均不超過10000。

輸入樣例：

3 3

1 2 5

2 3 -3

1 3 4

輸出樣例：

優化思想：不需要更新每一條邊，隻需要将變動的邊影響的下一條邊更新就可以，用隊列來進行優化

代碼：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t = spfa();

    if (t == -1) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

最短路問題（單源+多源最短路問題）

最短路問題的幾種情況及實作模闆

最短路的常見情況總結及算法

樸素的Dijkstra算法：（注：若所有權重都相等，可以采取BFS寬度優先搜尋來找最短路）

堆優化版的Dijkstra算法

bellman_ford算法（存在負權變）note：處理最多經過k條邊的最短路徑隻能用此算法

spfa算法

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希