【数据结构】B : DS图应用--最短路径

B : DS图应用–最短路径

Description

给出一个图的邻接矩阵，再给出指定顶点v0，求顶点v0到其他顶点的最短路径

Input

第一行输入t，表示有t个测试实例
第二行输入n，表示第1个图有n个结点
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开
第四行输入v0，表示求v0到其他顶点的最短路径距离
以此类推输入下一个示例

Output

每行输出v0到某个顶点的最短距离和最短路径
每行格式：v0编号-其他顶点编号—-[最短路径]，具体请参考示范数据

Sample

Input

1
5
0 5 0 7 15
0 0 5 0 0
0 0 0 0 1
0 0 2 0 0
0 0 0 0 0
0
1
2
3
4
5
6
7
8

Output

0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 4 ]
1
2
3
4

解题思路：

首先先要了解图论里面单源最短路径的实现——Dijkstra算法，知道它是怎么一步步算出源点到每一个点的最短距离的，可以参考这个视频【算法】最短路径查找—Dijkstra算法，然后就看代码，对着视频来进行解释：

// Dijkstra算法实现
void Dijkstra(int start)
{
	memset(dis, 0x3f, sizeof(dis));
	memset(fixed, 0, sizeof(fixed));
	last[start] = -1;
	dis[start] = 0;
	int minDisNode, minDis;
	for (int i = 0; i < n; i++)
	{
		minDis = INF;
		for (int j = 0; j < n; j++)
			if (!fixed[j] && dis[j] < minDis)
				minDisNode = j, minDis = dis[j];
		fixed[minDisNode] = true;
		for (int j = 0; j < n; j++)
		{
			if (g[minDisNode][j] != 0 && minDis + g[minDisNode][j] < dis[j])
				dis[j] = minDis + g[minDisNode][j], last[j] = minDisNode;
		}
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

初始化

memset(dis, 0x3f, sizeof(dis));  // 设置所有节点到源点的初始距离为无穷大
memset(fixed, 0, sizeof(fixed)); // 初始化所有节点为未固定
last[start] = -1;                // 源点的上一个节点设置为-1
dis[start] = 0;                  // 源点到自身的距离设置为0
1
2
3
4

• dis[]数组存储从源点到每个节点的当前最短距离。初始时，除了源点到自身的距离为0外，所有其他距离都设置为无穷大。
• fixed[]数组用于标记节点是否已经找到了从源点出发的最短路径。
• last[]数组用于记录到达每个节点的最短路径上的前一个节点，对于源点而言，没有前一个节点，所以设置为-1。

主循环

for (int i = 0; i < n; i++)
{
    minDis = INF;
    for (int j = 0; j < n; j++)
        if (!fixed[j] && dis[j] < minDis)
            minDisNode = j, minDis = dis[j];
    fixed[minDisNode] = true;
    for (int j = 0; j < n; j++)
    {
        if (g[minDisNode][j] != 0 && minDis + g[minDisNode][j] < dis[j])
            dis[j] = minDis + g[minDisNode][j], last[j] = minDisNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 第一个for循环遍历所有节点，寻找最短路径。
• 内层的第一个for循环用于找到当前未固定节点中距离源点最近的节点minDisNode。
• fixed[minDisNode] = true;将找到的最短距离节点标记为已固定。
• 内层的第二个for循环进行“松弛操作”：通过minDisNode更新其他未固定节点的最短距离。如果通过minDisNode到某个节点的距离比当前记录的距离短，则更新该距离
• 松弛操作：if (g[minDisNode][j] != 0 && minDis + g[minDisNode][j] < dis[j])检查是否存在一条从minDisNode到j的边，并且通过这条边到达j的距离是否比当前记录的距离短。如果是，更新dis[j]为通过minDisNode到j的新距离，并记录last[j]为minDisNode。

心得：

一开始学这个算法的时候，可能会想到一个环，对于这个环，例如一个三个节点的环，现在节点一是源点，懵的地方就在于我在第一个次循环之后得出节点一到节点二最短，我就把节点二纳入fixed中，我就有疑惑，如果是一个环的话，那我从节点一到节点三再到节点二为什么不是最短。现在项想明白，在循环内层第一个for循环的时候，就已经挑选出最短的了，哪怕节点一到节点二和节点一到节点三的距离相等，节点三到节点二总不可能为负数吧。

明白这个算法的原理之后，后面的输出就很简单了，直接上代码吧。

AC代码

#include 
#include 
using namespace std;

const int INF = 999999; // 定义无穷大常量

void printShortestPath(int u, const vector<int>& previousNodes) {
    if (u == -1)
        return;
    printShortestPath(previousNodes[u], previousNodes);
    cout << u << " ";
    return;
}


void calculateShortestPaths(int start, const vector<vector<int>>& graph, int n) {
    vector<int> previousNodes(n, -1);
    vector<int> shortestDistances(n, INF);
    vector<int> visitedNodes(n, 0);

    shortestDistances[start] = 0;

    for (int i = 0; i < n; i++) {
        int minDistance = INF, nearestNode = -1;

        for (int j = 0; j < n; j++)
            if (!visitedNodes[j] && shortestDistances[j] < minDistance)
            {
                nearestNode = j;
                minDistance = shortestDistances[j];
            }

        visitedNodes[nearestNode] = 1;

        for (int j = 0; j < n; j++)
            if (graph[nearestNode][j] != 0 && minDistance + graph[nearestNode][j] < shortestDistances[j])
            {
                shortestDistances[j] = minDistance + graph[nearestNode][j];
                previousNodes[j] = nearestNode;
            }
    }

    for (int i = 0; i < n; i++) {
        if (i != start) {
            cout << start << "-" << i << "-" << shortestDistances[i];
            cout << "----[";
            printShortestPath(i, previousNodes);
            cout << "]" << endl;
        }
    }

    return;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<vector<int>> graph(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> graph[i][j];

        int sourceNode;
        cin >> sourceNode;
        calculateShortestPaths(sourceNode, graph, n);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71