題目大意：求圖上單點到單點之間的最短路。
題目分析：讓我們考慮沒有負邊的情況。在Bellman-Ford算法中，如果dist[i]還不是最短距離的話，那么即使進行dist[j]=dist[i]+(從i到j的邊的權值)的更新，dist[j]也不會變成最短距離。而且，即使dist[i]沒有變化，每一次循環也要檢查一遍從i出發的所有變。這顯然是很浪費時間的。因此可以對算法作如下修改。
（1）找到最短距離已經確定的頂點，從他出發更新相鄰頂點的最短距離。
（2）此后不再需要關心（1）中的“最短距離已經確定的頂點”。
在（1）和（2）中提到的“最短距離已經確定的”要怎么得到時問題的關鍵。在最開始時，只有起點的最短距離是確定的。而在尚未使用過的頂點中，距離dist[i]最小的頂點就會加入“最短距離已經確定的頂點”的陣營。這是因為由于不會存在負邊，所以dist[i]不會在之后的更新中變小。這個算法叫做Dijkstra算法。
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010;
typedef pair<
int,
int> P;
vector<P> G[maxn];
int V, E, dist[maxn];
bool vis[maxn];
void dijkstra(
int s) {
fill(dist, dist + V, INF);
fill(vis, vis + V,
false);
dist[s] = 0;
while(
true) {
int u = -1;
for(
int i=0;i<V;i++)
if(!vis[i] && (u == -1 || dist[i] < dist[u]))
u = i;
if(u == -1)
break;
vis[u] =
true;
int sz = G[u].size();
for(
int i=0;i<sz;i++) {
int v = G[u][i].first;
int w = G[u][i].second;
dist[v] = min(dist[v], dist[u] + w);
}
}
}
int main() {
scanf("%d%d" , &E, &V);
for(
int i=0;i<V;i++) G[i].clear();
for(
int i=0;i<E;i++) {
int u, v, w;
scanf("%d%d%d" , &u, &v, &w);
u --; v --;
G[u].push_back(make_pair(v, w));
G[v].push_back(make_pair(u, w));
}
dijkstra(0);
printf("%d\n", dist[V-1]);
return 0;
}
posted on 2015-02-13 19:34
JulyRina 閱讀(351)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告