数据结构图之最短路 Dijkstra 算法 - 实例2道PAT对

Cover

图片来自unsplash

前提

很早就决定要考PAT了，前几天刚刚报了秋季9.8的考试，所以接下来的重心也都放在了刷题学习算法上面。也希望能够把刷题的时候遇到的一些知识记录在博客里面。我是在牛客网上面刷的题，前两道就是关于图的最短路算法的变种，所以也乘机好好复习了一下相关的算法，将这两道题涉及到的Dijkstra算法做个详解。
同时分享一波学习资料，我的算法理解都是来自于这本书《挑战程序设计竞赛》，我将其放在百度云上面，有需要的朋友拿去下载（在本文最后，要下载的直接拖到最后面下载，不过建议看完本文）。 同时本文提到的算法在书中的101页，配合阅读效果更佳喔。

单源最短路

Dijkstra是针对单源最短路的算法，即该算法将会找出从某点出发到其他点的最短距离。

算法思想

1. 找出最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离。
2. 此后不在关心1中提到的最短距离已经确定的点。

其中，最短距离已经确定的顶点就是找出所有距离的基础，这个点就是起点它自己，它到自己的距离是0是在最开始的时候唯一确定的。而我们要做的事就是，不断的从最短距离已经确定的点出发，将它相邻的点的最短距离更新。

举个例子：设最开始的点为s，那么我们将会把s所有相邻的点的距离定为：从s到该点的距离。那么与s相邻的点的最短距离也就确定了。这时候我们就多了几个最短距离确定的点，然后我们从其他这些没有用过的点出发，再将其最短距离定为：从s到该点的最短距离 + 从该点到其相邻点的距离。

如何实现 - 设起点为s

1. 用二维数组cost来存储点到点的距离是多少，如果点之间没有路，那么就将两点之间距离设置为INF。
2. 用一维数组used来表示某个点有没有被访问过。
3. 用一维数组d来表示点到其他点的最短距离，初始化所有距离为INF。
4. 刚开始，d[s] = 0
5. 设变量v 为当前选定的点，初始化为-1。
6. 如果是第一次，则v = s，否则，在没有使用过的点中选择一个距离最小的点。
7. 如果v等于-1，则所有点被访问过了，跳出循环即可。如果不是，used[v] = true，表示已经访问过该点。
8. 遍历所有的点，将s到该点到距离设置为：s到该点的距离，s到v + v到该点的距离中最小的那个。
9. 从5 到8开始循环。

INF即无穷大，根据具体问题具体设置

ps：
若1 - 3 的距离为2，那么cost[1][3] = cost[3[1] = 2。
若起点为点1，那么d[1] = 0，即点1到点1的距离，d[5]即点1到点5的距离。

实现代码

根据上面实现的9条，翻译过来就是其代码：

int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;     //顶点个数

void dijkstra() {
    fill(d, d + V, INF);
    fill(used, used + V, false);
    d[s] = 0;
    
    while(true) {
        int v = -1;
        
        for(int u = 0; u < V; u++) {
            if(!used[u] && (v == -1 || d[u] < d[v]))
            v = u;
        }
        
        if(v == -1) break;
        used[v] = true;
        
        for(int u = 0; u < V； u++) {
            d[u] = min(d[u], d[v] + cost[v][u]);
        }
    }
}

是不是很短，那如果要记录路径呢？
跟数组d一样，设置一个path数组，放路径。然后在while外面设置path[s] = (string)s，在第二个for循环里面，如果要更新d[u]，那么也将path[u]更新了，更新为 path[u] = path[v] + (string)u

两道PAT真题

题目描述与解决代码分别是：

1. Public Bike Management (30) - Solve
2. All Roads Lead to Rome (30 - Solve

PDF书下载地址

挑战程序设计-pdf - 百度云下载链接(失效回复)