本文實例為大家分享了C語言求解無向圖頂點之間的所有最短路徑的具體代碼，供大家參考，具體內容如下
思路一：
DFS，遇到終點之后進行記錄
輔助存儲：
std::vector<int> tempPath;std::vector<std::vector<int>> totalPath;
實現：
//查找無向圖的所有最短路徑，直接dfs就可以解決了//記錄保存這里用 vector<vector<int>> 插入失敗，重新搞一下 OK// 時間復雜度 O（N + E）#include <iostream>#include <cstdio>#include <cstdlib>#include <vector>#include <set>#define MAX 10#define INF 999999int graph[MAX + 1][MAX + 1];int N, M; //node, edgeint nodeBook[MAX + 1];int minPath = INF;std::vector<int> pathNodeVec;std::vector<std::vector<int>> allShortVec;int startNode, endNode;void dfs(int i, int step){ if (i == endNode) { //遇到終點，進行路徑判定 if (step < minPath) { std::cout << "step < minpath.., size = " << allShortVec.size() << std::endl; minPath = step; pathNodeVec.push_back(i); for (auto &elem : pathNodeVec) std::cout << elem << "/t"; std::cout << std::endl; std::vector<int> tempVec = pathNodeVec; allShortVec.clear(); //清空 allShortVec.push_back(tempVec); //存儲 pathNodeVec.pop_back(); } else if (step == minPath) { std::cout << "step == minpath.., size = " << allShortVec.size() << std::endl; pathNodeVec.push_back(i); for (auto &elem : pathNodeVec) std::cout << elem << "/t"; std::cout << std::endl; std::vector<int> tempVec = pathNodeVec; allShortVec.push_back(tempVec); //存儲當前路徑 pathNodeVec.pop_back(); } else { ;} return; } nodeBook[i] = 1; pathNodeVec.push_back(i); for (int x = 1; x <= N; x++) { //嘗試所有可能性 if (x == i) continue; if (nodeBook[x] == 1) continue; if (graph[i][x] == INF) continue; dfs(x, step + 1); } nodeBook[i] = 0; pathNodeVec.pop_back(); return ;}int main(void){ std::cin >> N >> M; for (int x = 1; x <= N; x++) nodeBook[x] = 0; //表示還沒有訪問 for (int x = 1; x <= N; ++x) for (int y = 1; y <= N; ++y) { if (x == y) graph[x][y] = 0; else graph[x][y] = INF; } for (int i = 1; i <= M; ++i) { int tempX, tempY, tempWeight; std::cin >> tempX >> tempY >> tempWeight; graph[tempX][tempY] = tempWeight; } std::cout << "please input start node & end node :" << std::endl; std::cin >> startNode >> endNode; pathNodeVec.clear(); allShortVec.clear(); dfs(startNode, 0); std::cout << "all shortest path: /t"; std::cout << "size = " << allShortVec.size() << std::endl; for (std::vector<std::vector<int>>::const_iterator it = allShortVec.begin(); it != allShortVec.end(); it++) { for (std::vector<int>::const_iterator it2 = (*it).begin(); it2 != (*it).end(); it2++) std::cout << (*it2) << "/t"; std::cout << std::endl; } getchar(); return 0;}時間分析：
O(V + E)
缺點：
可能會爆棧，我這里算86W點+414W邊直接爆，小的沒問題。
思路二：
BFS，位圖/vector/.. 記錄好每一步的路徑即可
時間
O(V + E)
額外開銷：
存儲每一步的路徑，如何維護好，盡量避免循環查找。
思路三：
1. 先求出起始點start到其余所有點的最短路徑； Dijkstra
2. 然后以終點end為開始，反向進行dfs/bfs搜索；
每回退 i 層，判斷值（path-i）與起點到當前點最短路徑長度 temp 的比較；
二者相等，則繼續（利用子問題的正確性）； 若 （path-i） < temp ，則這個點不在最短路徑上，放棄。
如圖所示：
先求出start到其余所有點的最短路徑；
然后從 end 點開始往回搜索；
end上面一個點，（path - 1 = 3）等于起始點到它的最短路徑長 3，判斷，是最短路徑上的點，繼續；
再往上搜索：
左邊那個點3，因為此時（path - 2）= 2，而那個點的 temp=3，即 （path - i） < temp ，因此那個點一定不在 start 到 end 的最短路徑上。
而上面那個點2，此時 （path - 2）= 2 ， 而那個點 temp = 2， 即 （path - i） == temp ， 因此它必然在 start 到 end 的最短路徑上。繼續搜索下去 。
重復這樣的過程直到搜索完畢，最終得到兩條最短路徑。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
圖片精選
