圖的構(gòu)造

#include <vector> #include <iostream>using namespace std;struct edge{int to, cost; };const int MAX = 1000;vector<edge> G[MAX]; // 圖 int V; // 頂點數(shù) int E; // 邊數(shù)void creat(){// 因為只是支持頂點 0 ~ n， 如果頂點是 1 ~ n, 自行更改 只要把頂點的值減 1 就行了// 這里假設(shè)是 0 ~ ncin >> V >> E;for(int i = 0; i < E; ++i){int from, to, cost;cin >> from >> to >> cost;edge e;e.to = to;e.cost = cost;G[from].push_back(e);} }int main(){creat();return 0; }

Dijkstra算法(未經(jīng)優(yōu)化)

#include <vector> #include <iostream>using namespace std;struct edge{int to, cost; };const int MAX = 10001; const int INF = 0x3f3f3f3f; // 假設(shè)這是無法到達的話的距離vector<edge> G[MAX]; // 圖 int d[MAX]; int used[MAX]; int V; // 頂點數(shù) int E; // 邊數(shù) int s; // 出發(fā)的點void creat(){// 因為只是支持頂點 0 ~ n， 如果頂點是 1 ~ n, 自行更改 只要把頂點的值減 1 就行了// 這里假設(shè)是 0 ~ ncin >> V >> E >> s;for(int i = 0; i < E; ++i){int from, to, cost;cin >> from >> to >> cost;edge e;e.to = to;e.cost = cost;G[from].push_back(e);} }void Dijkstra(int s){fill(d, d + V, INF);fill(used, used + V, false);d[s] = 0;while(true){int v = -1;for(int i = 0; i < V; ++i){if(!used[i] && (v == -1 || d[v] > d[i])){ // 尋找到達某一點的最短距離v = i;}}if(v == -1) break;used[v] = true;for(int i = 0; i < (int)G[v].size(); ++i){edge e = G[v][i];if(d[v] != INF) // 如果存在不能到達的點的話，則不予考慮d[e.to] = min(d[e.to], d[v] + e.cost); // v -> i 從v到 e.to頂點的距離}} }void solve(){creat();Dijkstra(s);for(int i = 0; i < V; ++i) cout << d[i] << ' '; // 輸出到達各個頂點的最短距離， 如果無法到達結(jié)果為 INF }int main(){solve();return 0; }

Dijkstra(優(yōu)先隊列的優(yōu)化)

#include <vector> #include <iostream> #include <queue> #include <utility>using namespace std;struct edge{int to, cost; };typedef pair<int, int> P; const int MAX = 10001; const int INF = 0x3f3f3f3f; // 假設(shè)這是無法到達某一點的距離vector<edge> G[MAX]; // 圖 int d[MAX]; int used[MAX]; int V; // 頂點數(shù) int E; // 邊數(shù) int s; // 出發(fā)的點void creat(){// 因為只是支持頂點 0 ~ n， 如果頂點是 1 ~ n, 自行更改 只要把頂點的值減 1 就行了// 這里假設(shè)是 0 ~ ncin >> V >> E >> s;for(int i = 0; i < E; ++i){int from, to, cost;cin >> from >> to >> cost;edge e;e.to = to;e.cost = cost;G[from].push_back(e);} }void Dijkstra(int s){priority_queue<P, vector<P>, greater<P> > que; // 要空一個格fill(d, d + V, INF);que.push(P(0, s));d[s] = 0;while(!que.empty()){P p = que.top(); que.pop();int v = p.second; // first 儲存最短距離 second 儲存的是頂點的坐標(biāo)if(d[v] < p.first) continue; // 一直尋找，直到找到符合最短距離的 v 點for(int i = 0; i < (int)G[v].size(); ++i){edge e = G[v][i]; // v -> e.to 的邊if(d[e.to] > d[v] + e.cost){d[e.to] = d[v] + e.cost;que.push(P(d[e.to], e.to));}}} }void solve(){creat();Dijkstra(s);for(int i = 0; i < V; ++i) cout << d[i] << ' '; // 輸出到達各個頂點的最短距離， 如果無法到達結(jié)果為 INF }int main(){solve();return 0; }

SPFA

#include <vector> #include <iostream> #include <queue>using namespace std;struct edge{int to, cost; };const int MAX = 10001; const int INF = 0x3f3f3f3f; // 假設(shè)這是無法到達某一點的距離vector<edge> G[MAX]; // 圖 int visit[MAX]; // 是否訪問了 int d[MAX]; int used[MAX]; int V; // 頂點數(shù) int E; // 邊數(shù) int s; // 出發(fā)的點void creat(){// 因為只是支持頂點 0 ~ n， 如果頂點是 1 ~ n, 自行更改 只要把頂點的值減 1 就行了// 這里假設(shè)是 0 ~ ncin >> V >> E >> s;for(int i = 0; i < E; ++i){int from, to, cost;cin >> from >> to >> cost;edge e;e.to = to;e.cost = cost;G[from].push_back(e);} }void BFS_Dijkstra(int s){queue<int> que;fill(d, d + V, INF);que.push(s);d[s] = 0;while(!que.empty()){int v = que.front(); que.pop();visit[v] = 0; // 回溯 回到 v 點, 再繼續(xù)向其他點擴展for(int i = 0; i < (int)G[v].size(); ++i){edge e = G[v][i];if(d[e.to] > d[v] + e.cost){d[e.to] = d[v] + e.cost;if(!visit[e.to]){visit[e.to] = 1;que.push(e.to);}}}} }void solve(){creat();BFS_Dijkstra(s);for(int i = 0; i < V; ++i) cout << d[i] << ' '; // 輸出到達各個頂點的最短距離， 如果無法到達結(jié)果為 INF }int main(){solve();return 0; }

Bellman_Ford算法

#include <iostream> #include <cstring>using namespace std;// 邊 struct edge{int from, to, cost; };const int INF = 0x3f3f3f3f; const int V_MAX = 10001; // 頂點的最大數(shù)目 const int E_MAX = 10001; // 邊的最大數(shù)目 int V; // 頂點數(shù) 一樣是 0 ~ n int E; // 邊數(shù) int s; // 起點 edge es[E_MAX]; int d[V_MAX];void creat(){ // 構(gòu)造圖， 另一種構(gòu)建方法cin >> V >> E >> s;for(int i = 0; i < E; ++i){cin >> es[i].from >> es[i].to >> es[i].cost; // from -> to 的邊的距離 = cost} }void Bellman_Ford(int s){fill(d, d + V, INF);d[s] = 0;while(true){bool update = false;for(int i = 0; i < E; ++i){edge e = es[i];if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){ // 不斷尋找到達e.to 的最短距離d[e.to] = d[e.from] + e.cost;update = true;}}if(!update) break; // 如果沒有最短的路徑可尋找了， 退出！} }// 求負圈的算法 // 因為最短路不會經(jīng)過同一個點兩次（也就是說罪過通過 V - 1條邊，whlie(true) 最多執(zhí)行 V - 1次） // 反之，如果存在從 s 可達的負圈，那么在第 | V |次循環(huán)中也會更新 d 的值bool find_negative_loop(){memset(d, 0, sizeof(d));for(int i = 0; i < V; ++i){for(int j = 0; j < E; ++j){edge e = es[j];if(d[e.to] > d[e.from] + e.cost){d[e.to] = d[e.from] + e.cost;if(i == V - 1) return false;}}}return true; }void solve(){creat();Bellman_Ford(s);for(int i = 0; i < V; ++i) cout << d[i] << ' '; // 輸出最短距離 }int main(){solve();return 0; }

總結(jié)

以上是生活随笔為你收集整理的单源最短路径（C++实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。