记不清这是第多少次总结最短路问题了

记不清这是第多少次总结最短路问题了，不过每次总结也都能有新的收获吧。

这次是总结当作模板使用的。

Bellman算法：

维护一个数组，记录从起点到其他点的距离，不断通过可能的路径来更新数组，直到遍历了所有的路径，从而找到最小值。

// 最短路 Bellman-Ford 算法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000+7;
const int INF = 0x3f3f3f3f;

struct edge{
    int from, to, cost;
};

int n, m;   // n个顶点，m条边
edge G[MAXN];
int dis[MAXN];

void Bellman()
{
    fill(dis, dis+MAXN, INF);
    dis[1] = 0;
    while(1) 
    { 
        bool update = false;
        for(int i=0; i<m; i++)
        {
            edge e = G[i];
            if(dis[e.from] != INF && dis[e.from] + e.cost < dis[e.to])
            {
                dis[e.to] = dis[e.from] + e.cost;
                update = true;
            }
        }
        if(!update)
            break;
    }
}


int main()
{
    while(scanf("%d %d", &n, &m) != EOF)
    {
        for(int i=0; i<m; i++)
        {
            scanf("%d %d %d", &G[i].from, &G[i].to, &G[i].cost);
        }
        Bellman();
        printf("%d\n", dis[n]);
    }


    return 0;
}

Dijkstra算法：

每次取已经确定的最短路，在已知的最短路的基础上寻找下一个距离最近的点，知道找到所有的点。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;

int n, m;   // n个顶点， m条边
int G[N][N];    // 存图
bool used[N];   // 标记点是否走过
int dis[N];     // 起点到其他点的距离

void djk(int s)     // s为指定的一个起点
{
    // 首先要初始化
    for(int i=0; i<N; i++)
    {
        used[i] = 0;
        dis[i] = INF;
    }
    dis[s] = 0;     // 应该把起点的距离置为0

    while(1)
    {
        int v = -1;
        // 从未使用过的点中找到一个距离最近的点
        for(int i=1; i<=n; i++)
        {
            if(!used[i] && (v == -1 || dis[i] < dis[v]))
                v = i;
        }
        if(v == -1 )    break; // 如果所有的点都已经访问过了
        used[v] = 1;
        for(int i=1; i<=n; i++)
            dis[i] = min(dis[i], dis[v] + G[v][i]);

    }
}

int main()
{
    while(scanf("%d %d", &n, &m) != EOF)
    {
        memset(G, INF, sizeof(G));
        int a, b, c;
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d", &a, &b, &c);
            G[a][b] = c;
        }
        djk(1);
        printf("%d\n", dis[n]);
    }


    return 0;
}

优先队列优化的 Dijkstra算法：

Dijkstra算法每次都重新遍历了一遍所有的点来找距离最近的点，使用优先队列可以优化这一问题。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;

struct edge{        // 邻接表存图，一次存两个属性
    int to, cost;
};
typedef pair<int, int> P;   // 优先队列内的节点需要两个值，first是最小距离, second是顶点编号
int n, m;
vector<edge> G[N];  // 邻接表
int dis[N];     // 从起点到其他点的最短距离

void djk(int s)
{
    priority_queue<P, vector<P>, greater<P> > q;    // 优先队列
    // 首先初始化
    for(int i=0; i<N; i++)
        dis[i] = INF;
    dis[s] = 0;
    
    q.push(P(0, s));    // 把起点放入队列中
    while(!q.empty())
    {
        P p = q.top();  q.pop();
        int v = p.second;   // 取出顶点
        if(dis[v] < p.first)    
            continue;
        for(int i=0; i<G[v].size(); i++)    // 遍历所以与当前点有边的点
        {
            edge e= G[v][i];
            if(dis[e.to] > dis[v] + e.cost) 
            {
                dis[e.to] = dis[v] + e.cost;
                q.push(P(dis[e.to], e.to));
            }
        }
    }

}

int main()
{
    while(scanf("%d %d", &n, &m) != EOF)
    {
        int a;
        edge b;
        for(int i=0; i<m; i++)
        {
            scanf("%d %d %d", &a, &b.to, &b.cost);
            G[a].push_back(b);
        }
        djk(1);
        printf("%d\n", dis[n]);
    }



    return 0;
}

上面都是单源最短路问题，接下来的是任意两点间的最短路问题。

Floyd算法：

// Floyd 任意两点最短路算法
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;

int n, m;
int dp[N][N];

void floyd()
{    
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);

}

int main()
{
    while(scanf("%d %d", &n, &m) != EOF)
    {
        for(int i=0; i<N; i++)  // 对邻接矩阵的初始化
        {
            for(int j=0; j<N; j++)
            {
                if(i == j)  dp[i][j] = 0;
                else dp[i][j] = INF;
            }
        }

        int a, b, c;
        for(int i=0; i<m; i++)
        {
            scanf("%d %d %d", &a, &b, &c);
            dp[a][b] = dp[b][a] = c;    // 无向图必须必须双向
        }
        floyd();
        printf("%d\n", dp[1][8]);
        printf("%d\n", dp[8][1]);
    }


    return 0;
}