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

Output

0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 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;
}

初始化

memset(dis, 0x3f, sizeof(dis));  // 設置所有節點到源點的初始距離為無窮大
memset(fixed, 0, sizeof(fixed)); // 初始化所有節點為未固定
last[start] = -1;                // 源點的上一個節點設置為-1
dis[start] = 0;                  // 源點到自身的距離設置為0

• 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;}
}

• 第一個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 <iostream>
#include <vector>
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;
}