【数据结构\图】最短路径

定义： 带权图中从一个顶点到另一个顶点的权值和最小的路径，无权图中路径长度最小的路径（可视为边权为1）

Dijkstra: 适用范围：非负权图的单源最短路径。

描述： 将图顶点集分为2个集合 $S$（该集合里的顶点 $x$ 都已求出源点 $v$ 到顶点 $x$ 的最短路径）和 $U$（该集合表示暂未处理）,每次处理时，从 $U$ 中选出一个顶点 $u$ ,使得 ( $S$中顶点 ) $\Longrightarrow$ $u$ 的距离最短，将 $u$ 加入 $S$ 中，并更新 $U$ 中所有顶点 $x$ 的 当前 $S$ 与 $x$ 的最短距离，直到所有顶点都已加入 $S$ 中。

过程： 1.初始时设置 $S={v}$ ( $v$ 是源点),声明数组 dist[N]， dist[i] 代表当前 S 到 顶点 i 的最短距离，初始设置 dist[v] = 0, 其余dist[i] 是 $v \Longrightarrow i$ 的权值（无边时为INF） 2.从 dist 中 选出最小值所对应的顶点 $u$（$u \notin S$）,对 $u$ 进行 加入 $S$ 操作。即book[u]=1, 以及对 $U$ 中其余顶点 $i$ 做 松弛 操作： dist[i] = min(dist[i],dist[u]+g[u][i]) 其中g为该图的领接矩阵。 3.直到所有顶点都加完 即 循环次数为 $n - 1$ 次。 路径使用 $path[i]$ 表示从 $v$ 到该顶点 $i$ 的路径中 $i$ 的前一个顶点。(与dist同理，都表示的是当前值，会根据松弛结果进行更新)

图可视化的一个网站

代码如下：

/* 注意本例的顶点编号是从0开始的 */

#include <iostream>
#include <vector>
#include <stack>

#define INF 98889

using namespace std;

void Dijkstra(const vector<vector<int>> &matrix, int,int);

int main() {
    vector<vector<int>> matrix;
    int n;
    int m;
    cin>>n>>m;
    matrix.assign(n,vector<int>(n,INF));
    int u,v,w;
    for(int i = 0; i < n ; i++)
    {
        matrix[i][i] = 0;
    }
    for (int i = 0; i < m; i++) {
        cin>>u>>v>>w;
        matrix[u][v] = w;
    }
    cin>>v>>u;
    Dijkstra(matrix,v,u);
}

void Dijkstra(const vector<vector<int>> &matrix, int v,int dst) {
    // init
    int n = matrix.size();
    vector<int> book(n,0),dist(n,INF);
    vector<int> path;
    book[v] = 1;
    dist[v] = 0;

    path.resize(n,-1);


    for(int i = 0; i < n; i++)
    {
        if(matrix[v][i]<INF)
        {
            path[i] = v; /* 初始化时 如果<v,i>有路径，则设置当前的情况下 i前一个顶点为v */
        }
        dist[i] = matrix[v][i];
    }
    int u = -1;
    // 执行 n - 1 次 每次都加入一个顶点到 S 中
    for(int i = 1;i<n;i++)
    {
        // 找出当前S距离U的dist最小的U中的点
        int min_dist = INF;
        for(int j = 0;j<n;j++)
        {
            if(book[j]==0 and dist[j]<min_dist)
            {
                min_dist = dist[j];
                u = j;
            }
        }

        book[u] = 1; /* 加u入S */

        // 松弛操作 更新dist path
        for(int j = 0; j < n; j++)
        {
            if(book[j]==0)
            {
                if(matrix[u][j] < INF and dist[j]>dist[u]+matrix[u][j])
                {
                    dist[j] = dist[u] + matrix[u][j];
                    path[j] = u; /* 更新当前path下 j结点的前置顶点为u */
                }
            }
        }
    }

    // 使用栈 将逆序存储的path顺序输出

    stack<int> outpath;
    int tmp = dst;
    while(tmp != v)
    {
        outpath.emplace(tmp);
        tmp = path[tmp];
    }
    outpath.emplace(tmp);

    while(!outpath.empty())
    {
        cout<<outpath.top()<<" ";
        outpath.pop();
    }
    cout<<dist[dst]<<endl;
}

Floyd

算法描述 见oi-wiki

由于该式相当于一个迭代递推式，因此k的那个维可以省略。 不带路径记录：

#include <iostream>
#include <vector>
#include <cstring>
#include <iomanip>

using namespace std;

#define MAXN 100
int f[MAXN][MAXN];

int main()
{
    int n,m;
    cin>>n>>m;
    int x,y,w;
    memset(f,0x3f3f,sizeof(f));
    for(int i =1;i<=m;i++)
    {
        cin>>x>>y>>w;
        f[x][y] = w;
    }

    for(int k = 1; k<n;k++)
    {
        for(int x=0;x<n;x++)
        {
            for(int y=0;y<n;y++)
            {
                f[x][y] = min(f[x][y],f[x][k]+f[k][y]);
            }
        }
    }

    for(int i = 0; i<n;i++)
    {
        for(int j = 0;j<n;j++)
        {
            cout<<setw(20)<<f[n-1][i][j];
        }
        cout<<endl;
    }
}

$path[i][j]$ 代表当前 $k-1$ （外层循环次数，递推的变量）来说， $i->j$ 这个最短路径的 $j$ 的前一个顶点，若 经过 $k$ 会 更短 则更新$path[i][j] = path[k][j]$

带路径记录(与dij类似)：

#include <iostream>
#include <vector>
#include <cstring>
#include <iomanip>
#include <stack>

using namespace std;

#define MAXN 100
int f[MAXN][MAXN],path[MAXN][MAXN];

int main()
{
    int n,m;
    cin>>n>>m;
    int x,y,w;
    for(int i = 0;i<n;i++)
    {
        for(int j = 0; j < n; j++)
        {
            path[i][j] = -1;
        }
    }
    memset(f,0x3f3f,sizeof(f));
    for(int i =1;i<=m;i++)
    {
        cin>>x>>y>>w;
        f[x][y] = w;
        path[x][y] = x;
    }

    for(int k = 1; k<n;k++)
    {
        for(int x=0;x<n;x++)
        {
            for(int y=0;y<n;y++)
            {
                if(f[x][y]>f[x][k]+f[k][y])
                {
                    f[x][y] = f[x][k] + f[k][y];
                    path[x][y] = path[k][y];
                }
            }
        }
    }

    cin>>x>>y;
    int tmp = path[x][y];
    stack<int> pathout;
    pathout.emplace(y);
    while(tmp!=x)
    {
        pathout.emplace(tmp);
        tmp=path[x][tmp];
    }
    pathout.emplace(x);
    while(!pathout.empty())
    {
        cout<<pathout.top()<<" ";
        pathout.pop();
    }
}