【題目鏈接】

ybt 1381：城市路(Dijkstra)

【題目考點】

1. 圖論 單源最短路徑

圖中有V個頂點E條邊，單源最短路徑算法
時間復雜度：

• 樸素Dijkstra算法：$O(V^2)$
• Dijkstra堆優化算法：$O(ElogE)$
• SPFA算法：一般情況下$O(kE)$，k為頂點平均入隊次數，最壞情況下$O(VE)$

空間復雜度：

• 鄰接矩陣：$O(V^2)$
• 鄰接表：$O(V+E)$

【解題思路】

最短路模板題，可以使用樸素Dijkstra算法，Dijkstra堆優化算法，SPFA算法
該題頂點數量為2000，如用鄰接矩陣存儲，需要$2000?2000?4B$，共15MB左右，空間復雜度過高。因此只能選用鄰接表。
鄰接表有：vector數組寫法及鏈式前向星寫法。

【題解代碼】

解法1：樸素Dijkstra算法

• vector數組實現鄰接表

#include<bits/stdc++.h> using namespace std; #define N 2005 struct Edge//邊結點 {int t, w;Edge(){}Edge(int a, int b):t(a),w(b){} }; vector<Edge> edge[N];//鄰接表 int n, m;//n:頂點數 m:邊數 int dis[N];//dis[i]:源點到頂點i的最短路徑 bool vis[N];//vis[i]:源點到頂點i的最短路徑是否已經確定 void init()//生成無向圖 {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;edge[f].push_back(Edge(t, w));edge[t].push_back(Edge(f, w));} } void dijkstra(int v0)//v0：源點 {memset(dis, 0x3f, sizeof(dis));dis[v0] = 0;for(int k = 1; k <= n; ++k){int u = 0;for(int i = 1; i <= n; ++i){if(vis[i] == false && (u == 0 || dis[i] < dis[u]))u = i; }vis[u] = true;for(int i = 0; i < edge[u].size(); ++i){int v = edge[u][i].t, w = edge[u][i].w;if(vis[v] == false && dis[v] > dis[u] + w)dis[v] = dis[u] + w;}} } int main() {init();dijkstra(1);cout << dis[n];return 0; }

• 鏈式前向星實現鄰接表

#include<bits/stdc++.h> using namespace std; #define N 2005 #define M 20005//無向圖，每條邊用兩個邊結點，所以M為m最大值10000的2倍 struct Edge//邊結點 {int t, w, next;Edge(){}Edge(int a, int b):t(a),w(b){} }; Edge edge[M];//結點池 int head[N], p = 1;//head:頭結點數組 p:結點池指針 int n, m;//n:頂點數 m:邊數 int dis[N];//dis[i]:源點到頂點i的最短路徑 bool vis[N];//vis[i]:源點到頂點i的最短路徑是否已經確定 void addEdge(int u, int v, int w)//在鄰接表中添加一個邊結點，在頭結點u后面的鏈表中用頭插法添加邊結點v {int np = p++;edge[np].t = v;edge[np].w = w;edge[np].next = head[u];head[u] = np; } void init()//生成無向圖 {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;addEdge(f, t, w);addEdge(t, f, w);} } void dijkstra(int v0)//v0：源點 {memset(dis, 0x3f, sizeof(dis));dis[v0] = 0;for(int k = 1; k <= n; ++k){int u = 0;for(int i = 1; i <= n; ++i){if(vis[i] == false && (u == 0 || dis[i] < dis[u]))u = i; }vis[u] = true;for(int i = head[u]; i != 0; i = edge[i].next){int v = edge[i].t, w = edge[i].w;if(vis[v] == false && dis[v] > dis[u] + w)dis[v] = dis[u] + w;}} } int main() {init();dijkstra(1);cout << dis[n];return 0; }

解法2：SPFA算法

• vector數組實現鄰接表

#include<bits/stdc++.h> using namespace std; #define N 2005 struct Edge {int t, w; Edge(){}Edge(int a, int b):t(a),w(b){} }; vector<Edge> edge[N]; bool vis[N];//vis[i]：頂點i是否在隊列中 int n, m, dis[N];//dis[i]：當前情況下v0到i的最短路徑距離 void initGraph() {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;//從f到t權值w edge[f].push_back(Edge(t, w));edge[t].push_back(Edge(f, w));} } void spfa(int sv)//sv起始點 {memset(dis, 0x3f, sizeof(dis));//dis初始值為INFqueue<int> que;dis[sv] = 0; vis[sv] = true;que.push(sv);while(que.empty() == false){int u = que.front();que.pop();vis[u] = false;for(int i = 0; i < edge[u].size(); ++i){int v = edge[u][i].t, w = edge[u][i].w;if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w;if(vis[v] == false){vis[v] = true;que.push(v);}}}} }int main() {initGraph();spfa(1);cout << dis[n];return 0; }

• 鏈式前向星實現鄰接表

#include<bits/stdc++.h> using namespace std; #define N 2005 #define M 20005//無向圖，每條邊用兩個邊結點，所以M為m最大值10000的2倍 struct Edge//邊結點 {int t, w, next;Edge(){}Edge(int a, int b):t(a),w(b){} }; Edge edge[M];//結點池 int head[N], p = 1;//head:頭結點數組 p:結點池指針 bool vis[N];//vis[i]：頂點i是否在隊列中 int n, m, dis[N];//dis[i]：當前情況下v0到i的最短路徑距離 void addEdge(int u, int v, int w)//在鄰接表中添加一個邊結點，在頭結點u后面的鏈表中用頭插法添加邊結點v {int np = p++;edge[np].t = v;edge[np].w = w;edge[np].next = head[u];head[u] = np; } void initGraph() {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;//從f到t權值w addEdge(f, t, w);addEdge(t, f, w);} } void spfa(int sv)//sv起始點 {memset(dis, 0x3f, sizeof(dis));//dis初始值為INFqueue<int> que;dis[sv] = 0; vis[sv] = true;que.push(sv);while(que.empty() == false){int u = que.front();que.pop();vis[u] = false;for(int i = head[u]; i != 0; i = edge[i].next){int v = edge[i].t, w = edge[i].w;if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w;if(vis[v] == false){vis[v] = true;que.push(v);}}}} }int main() {initGraph();spfa(1);cout << dis[n];return 0; }

解法2：Dijkstra堆優化算法

• vector數組實現鄰接表

#include<bits/stdc++.h> using namespace std; #define N 2005 struct Pair {int u, d;//u:頂點 d:距離 Pair(){}Pair(int a, int b):u(a),d(b){}bool operator < (const Pair &b) const//優先隊列中 d更小的更優先 {return b.d < d;} }; struct Edge {int t, w; Edge(){}Edge(int a, int b):t(a),w(b){} }; vector<Edge> edge[N]; bool vis[N];//vis[i]表示從v0到i點的最短路徑是否已經確定 int n, m, dis[N];//v0:源點 dis[i]：當前情況下v0到i的最短路徑距離 void initGraph() {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;//從f到t權值w edge[f].push_back(Edge(t, w));edge[t].push_back(Edge(f, w));} } void dijkstra(int sv)//sv起始點 {priority_queue<Pair> pq;//優先隊列中 d更小的更優先 memset(dis, 0x3f, sizeof(dis));//dis初始值為INFdis[sv] = 0;pq.push(Pair(sv, 0));while(pq.empty() == false){int u = pq.top().u;pq.pop();if(vis[u])//如果頂點u已經訪問過，則跳過 continue;vis[u] = true;for(int i = 0; i < edge[u].size(); ++i) {int v = edge[u][i].t, w = edge[u][i].w; if(vis[v] == false && dis[v] > dis[u] + w)//松弛{dis[v] = dis[u] + w;pq.push(Pair(v, dis[v]));}}} } int main() {initGraph();dijkstra(1);cout << dis[n];return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1381：城市路(Dijkstra)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。