Dijkstra的实现有很多种，下面给出一种较为简洁和高效的实现，可以作为模板快速使用。
1. 使用邻接表存储图；
2. 使用标准STL的vector存储每个点的所有邻接边；
3. 使用pair记录当前搜索的点，pair<int,int>对：
first记录最小距离，用以在优先队列中实现类似'最小堆优化'；
second记录该最小距离对应的点；
4. 使用priority_queue实现优化；(附使用方法)
5. 一个细节:这是盲目检索，中途若D[i] < p.first，说明队列里的该点已经到达了，这个pair已经无效，直接continue；
实现：
#include<bits/stdc++.h>
#define INF 100000005
#define MAX 100006
using namespace std; typedef pair<int,int> P; struct edge{
int to;
int cost;
edge(int t,int c):to(t),cost(c){
}
}; const int N = ;
vector<edge> g[N];
int D[N]; //距离
int n,m; //n个点 m条边 void Dijkstra(int s){
priority_queue<P,vector<P>,greater<P> > que; //小端优先队列
fill(D,D+MAX,INF);//注意必须初始化为最大
D[s] = ;
que.push(P(,s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(D[v] < p.first) continue; //说明该点无需重复
for(int i = ;i<g[v].size();i++) {
//遍历所有后续边
edge e = g[v][i];
int to = e.to;
int cost = e.cost;
if(D[to] > D[v] + cost){
D[to] = D[v] + cost;
que.push(P(D[to],to));
}
}
}
} int main(){
cin>>n>>m;
int a,b,d;
//Vector<edge> g[MAX]的初始化
for(int i = ;i<MAX;i++) {
g[i].clear();
}
//距离D的初始化
//fill(D,D+MAX,INF) ;//等Dijkstra时再初始化也行
for(int i = ;i<m;i++){
cin>>a>>b>>d;
g[a].push_back(edge(b,d));
g[b].push_back(edge(a,d));
}
int s,t;//起点 终点
s = ;
t = n;
Dijkstra(s);
cout<<D[n]<<endl;
return ;
}
【Appendix】
priority_queue的使用方法：
- 对于基本数据：
- priority_queue<int> q;
- priority_queue<int,vector<int>,less<int> > q; //默认，less可以省
- 这创建的是‘大 ’优先队列，大的在top
- 取：q.top();
- 出：q.pop();
- 放：q.push(int);
- 创建‘小 ’优先队列：
- priority_queue<int,vector<int>,greater<int> > q;
- 对于结构体数据：
- 1. 结构体运算符重载
bool operator < (const struct1,const struct1) const{
return ?;
}
- 2. 定义cmp函数，做参数传入，更加灵活
bool cmp(struct1,struct2){
return ?;
}
priority_queue<struct1,vector<struct2>,cmp> q;