发现时间久了脑子稍微有点糊，今天不想总结新的面试知识了，为了保持工作热度，回顾一下以前学习的知识。所以在在这里稍微总结一下迪杰斯特拉算法。也称最短路算法。
一 基础版n^2实现
1
2
3
4
5
6
7
8
9
10
11
12
| memset(v, 0, sizeof(v));
for(int i = 0; i < n; i++)
d[i] = (i==0 ? 0 : INF);
for(int i = 0; i < n; i++) {
int x, m = INF;
for(int y = 0; y < n; y++)
if(!v[y] && d[y] <= m)
m = d[y], x = y;
v[x] = 1;
for(int y = 0; y < n; y++)
d[y] = min(d[y], d[x] + w[x][y]);
}
|
二 利用边集和优先级队列Mlog(N)实现
首先需要定义边，边的定义如下。
1
2
3
4
5
6
| struct DistNode {
int d, u;
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
}
}
|
使用优先级队列进行优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| priority_queue<Node> q;
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i++)
d[i] = INF;
d[1] = 0;
q.push(make_pair(d[1],1));
while(!q.empty()) {
Node t = q.top();q.pop();
if(vis[t.second])continue;
vis[t.second] = 1;
for(int i = 1;i <= n;i++)
if(!vis[i] && d[i] > t.first+G[t.second][i]) {
d[i] = t.first+G[t.second][i];
q.push(make_pair(d[i],i));
}
}
|
算法比较简单暂时先不做过多的讲解，然后更新这个主要还有一个原因就是回家了但是不想划水太严重。所以暂时先更新这个不带过多讲解的版本啦。等23号正式开始给暑期集训讲课的时候在对内容进行更深一步的优化。
