问题简介

最短路径问题：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。
对于无权图，可以假设每条边的权重是1。
这里分别介绍一下Dijkstra算法和Floyd算法。

Dijkstra算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，采用广度优先遍历，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

示例

我们需要求得上图中 $V_1$ 到各个顶点的最短距离（ $V=\{V_1, V_2, V_3, V_4, V_5, V_6\}$ ）。首先我们初始化两个集合， $T$ 和 $S$ 。 $T$ 为已经求得距离的顶点的集合， $S$ 为剩余顶点。初始的时候， $T=\{V_1\}$ ， $S=\{V-T\}$ 。
再初始化一个 $d i s t$ 数组，代表目前已经求得的最短距离：

然后。我们要找到与集合 $V_1$ 中元素距离最近的顶点，便是 $V_3$ ，距离为10。那么此时的“10”便是确定值了（因为目前离 $V_1$ 顶点最近的是 $V_3$ 顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 $V_1$ 顶点到 $V_3$ 顶点的路程进一步缩短了。假如 $V_1$ 通过 $V_x$ 再到 $V_3$ 距离更短，这与 $V_1$ 到各顶点距离最短的是 $V_3$ 矛盾，所以并不存在 $V_x$ ），我们将 $V_3$ 加入到集合 $T$ 中。
此时的 $T$ 被更新过了，那么代表 $d i s t$ 数组中的元素也要进行更新，可以发现顶点 $V_3$ 有一条弧为 $V_3, V_4>$ ，且 $V_1->V_3->V_4$ 的距离为60，比原来的 $V_1->V_4$ 的距离（ $\infty$ 代表无法到达）更小，所以将 $d i s t$ 数组进行更新：

蓝色的表明已经是确定值，不会再更改，红色表明该距离刚才才更新过。此时，我们重复上述操作，在未标蓝的距离中（ $\infty, 60, 30, 100$ ）找到最小的距离，为 $V_5$ ，距离是“30”。那么，将 $V_5$ 加入 $T$ 中，通过 $V_5$ 的边再次更新 $d i s t$ ：

然后继续循环：

这便是顶点 $V_1$ 到各个顶点的最短距离，其中，到 $V_2$ 的距离为 $\infty$ 代表着顶点 $V_1$ 无法到达 $V_2$ 。

代码

#include <iostream>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1e3 + 7;
int dist[maxn];
int edge[maxn][maxn];
bool visited[maxn];
int v, n, m;

void init(){
    memset(dist, INF, sizeof dist); // 源点到任意点的距离初始化为无穷大；
    memset(edge, INF, sizeof edge);
    memset(visited, false, sizeof visited);
}

void dijkstra(){
    for(int i = 0; i <= n; i++){
        dist[i] = edge[v][i]; // 找到和源点相连的顶点，然后将距离填入dist；
    }
    dist[v] = 0; // 源点自己到自己距离为0；
    visited[v] = true;
    for(int i = 2; i <= n; i++){
        int temp = INF;
        int u = v;
        for(int j = 1; j <= n; j++){ // 找到当前与源点相连，距离最小的顶点；
            if(!visited[j] && dist[j] < temp){
                u = j;
                temp = dist[j];
            }
        }
        visited[u] = true; // 标记这个点进入集合T；
        for(int j = 1; j <= n; j++){
            if (!visited[j] && edge[u][j] < INF){ // 在u的周围寻找边；
                int newdist = dist[u] + edge[u][j];
                if (newdist < dist[j]){ //要是能够使得dist数组变小，便更新dist；
                    dist[j] = newdist;
                }
            }
        }
    }
}

int main(){
    while(scanf("%d%d", &n, &m) && n && m){
        init();
        int x, y, t;
        for(int i = 1; i <= m; i ++){
            cin>>x>>y>>t;
            edge[x][y] = t;
        }
        v = 1; // v为源点；
        dijkstra();
        for(int k = 1; k <= n; k++){
            if (dist[k] == INF){
                cout<<"INF"<<' ';
            }else{
                cout<<dist[k]<<' ';
            }
        }
    }
}

Floyd算法

Floyd算法相对来说更容易理解一点。
首先初始化一个二维数组，保存目前顶点两两之间的距离，无法到达的顶点设为 $\infty$ 。
这里先贴代码：

#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f

using namespace std;
const int maxn = 1e3 + 7;
int G[maxn][maxn]; //存图;
int path[maxn][maxn]; //记录路径;
int n, m;

void init(){
    memset(G, INF, sizeof G);
    memset(path, -1, sizeof path);
    for ( int i = 0; i < maxn; i ++){
        G[i][i] = 0; //自己到自己的距离为0;
    }
}

void floyd(){
    for (int k = 1; k <= n; k ++){ //中间值;
        for (int i = 1; i <= n; i++){ //横坐标;
            for (int j = 1; j<= n; j++){ //纵坐标;
                if (G[i][j] > G[i][k] + G[k][j]){
                    G[i][j] = G[i][k] + G[k][j]; //如果经过k顶点的距离更短，就更新;
                    path[i][j] = k;
                }
            }
        }
    }
}

void print_path(int u, int v){
    cout<<u<<"->";
    while (path[u][v] != -1){
        u = path[u][v];
        cout<<u<<"->";
    }
    cout<<v<<endl;
}

int main(){
    while (scanf("%d%d", &n, &m) && n && m){
        init();
        int x, y, t;
        for (int i = 0; i < m; i++){
            scanf("%d%d%d", &x, &y, &t);
            G[x][y] = t;
        }
        floyd();
        for (int q = 1; q <= n; q++){
            if (G[1][q] == INF){
                cout<<"INF"<<' '<<endl;
                cout<<"无法到达"<<endl;
            }else{
                cout<<G[1][q]<<' '<<endl;
                print_path(1, q);
            }
        }
    }
}