本文實(shí)例為大家分享了C語(yǔ)言求解無(wú)向圖頂點(diǎn)之間的所有最短路徑的具體代碼，供大家參考，具體內(nèi)容如下
專注于為中小企業(yè)提供成都網(wǎng)站建設(shè)、網(wǎng)站制作服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)可克達(dá)拉免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了近1000家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
思路一：
DFS，遇到終點(diǎn)之后進(jìn)行記錄
輔助存儲(chǔ)：
std::vector tempPath;
std::vector> totalPath;
實(shí)現(xiàn)：
//查找無(wú)向圖的所有最短路徑，直接dfs就可以解決了
//記錄保存這里用 vector> 插入失敗，重新搞一下 OK
// 時(shí)間復(fù)雜度 O（N + E）
#include
#include
#include
#include
#include
#define MAX 10
#define INF 999999
int graph[MAX + 1][MAX + 1];
int N, M; //node, edge
int nodeBook[MAX + 1];
int minPath = INF;
std::vector pathNodeVec;
std::vector> allShortVec;
int startNode, endNode;
void dfs(int i, int step)
{
if (i == endNode) { //遇到終點(diǎn)，進(jìn)行路徑判定
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 tempVec = pathNodeVec;
allShortVec.clear(); //清空
allShortVec.push_back(tempVec); //存儲(chǔ)
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 tempVec = pathNodeVec;
allShortVec.push_back(tempVec); //存儲(chǔ)當(dāng)前路徑
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; //表示還沒(méi)有訪問(wèn)
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>::const_iterator it = allShortVec.begin(); it != allShortVec.end(); it++) {
for (std::vector::const_iterator it2 = (*it).begin(); it2 != (*it).end(); it2++)
std::cout << (*it2) << "\t";
std::cout << std::endl;
}
getchar();
return 0;
}
時(shí)間分析：
O(V + E)
缺點(diǎn)：
可能會(huì)爆棧，我這里算86W點(diǎn)+414W邊直接爆，小的沒(méi)問(wèn)題。
思路二：
BFS，位圖/vector/.. 記錄好每一步的路徑即可
時(shí)間
O(V + E)
額外開(kāi)銷：
存儲(chǔ)每一步的路徑，如何維護(hù)好，盡量避免循環(huán)查找。
思路三：
1. 先求出起始點(diǎn)start到其余所有點(diǎn)的最短路徑； Dijkstra
2. 然后以終點(diǎn)end為開(kāi)始，反向進(jìn)行dfs/bfs搜索；
每回退 i 層，判斷值（path-i）與起點(diǎn)到當(dāng)前點(diǎn)最短路徑長(zhǎng)度 temp 的比較；
二者相等，則繼續(xù)（利用子問(wèn)題的正確性）； 若 （path-i） < temp ，則這個(gè)點(diǎn)不在最短路徑上，放棄。
如圖所示：
先求出start到其余所有點(diǎn)的最短路徑；
然后從 end 點(diǎn)開(kāi)始往回搜索；
end上面一個(gè)點(diǎn)，（path - 1 = 3）等于起始點(diǎn)到它的最短路徑長(zhǎng) 3，判斷，是最短路徑上的點(diǎn)，繼續(xù)；
再往上搜索：
左邊那個(gè)點(diǎn)3，因?yàn)榇藭r(shí)（path - 2）= 2，而那個(gè)點(diǎn)的 temp=3，即 （path - i） < temp ，因此那個(gè)點(diǎn)一定不在 start 到 end 的最短路徑上。
而上面那個(gè)點(diǎn)2，此時(shí) （path - 2）= 2 ， 而那個(gè)點(diǎn) temp = 2， 即 （path - i） == temp ， 因此它必然在 start 到 end 的最短路徑上。繼續(xù)搜索下去 。
重復(fù)這樣的過(guò)程直到搜索完畢，最終得到兩條最短路徑。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
本文名稱：C語(yǔ)言求解無(wú)向圖頂點(diǎn)之間的所有最短路徑
轉(zhuǎn)載注明：
http://weahome.cn/article/gsgdjc.html
重慶分公司
重慶分公司
