算法学习笔记之图论：最短路问题
多源最短路Dijkstra
在Dijkstra算法中，我们将节点分为「已经求得最短路的点」和「还未求得最短路的点」两个集合。算法须求得所有点的最短路，故需循环n次。 在每次循环中从「还未求得最短路的点」中，找出其中距离源点最近的一个点，用这个点更新源点到其它所有点的距离。算法复杂读为O(n^2);
核心代码如下
int dijkstra(){
dist = 0;
for(int i = 0;i < n;i++){
auto t = -1;
for(int j = 1;j <= n;j++){
if(!st && (t == -1 || dist > dist))
t = j;
}
st = true;
for(int j = 1;j <= n;j++){
dist = min(dist,dist + g);
}
}
if(dist == INF)return INF;
else return dist;
}
注：
在最后用t更新其它节点时，那些比t先求得最短路的点其实不会被更新。
Dijkstra算法无法处理含有副权边的情况，原因见下。
考虑反例:
1 1 1
1───────2───────3────── 5
│ ▲
│ │
│ │
└───────────4─────┘
3 -2根据Dijkstra算法，求得的路径为1->3->5,路径长度为3，但如果走1->4->3->5，长度为2,所以在存在副权边时，Dijkstra算法无法求得正确解。
主要是因为Dijkstra算法每次从「还未求得最短路的点」(即st为false)的点中选取距离源点最近的点(即dist最小)。
初始化阶段所有点的dist最初始化为正无穷,dist被初始化为0;
在第一次循环中，会取t==1,更新过后，dist=0,dist=1,dist=3
在第二次循环中，会取t==2,更新过后，dist=0,dist=1,dist=2,dist=3
在第三次循环中，会取t==3,更新过后，dist=0,dist=1,dist=2,dist=3,dist=3
在第四次循环中，会取t==4,更新过后，dist=0,dist=1,dist=1,dist=3,dist=3
在第五次循环中，会取t==5,更新过后，dist=0,dist=1,dist=2,dist=3,dist=3
堆优化版Dijkstra
void dijkstra(){
priority_queue<PII,vector<PII>,greater<PII>> que;
que.push({0,1});
dist = 0;
while(!que.empty()){
auto curr = que.top();
que.pop();
auto t = curr.second;
auto dis = curr.first;
if(st)continue;
else st = true;
for(int i = h;i != -1;i = ne){
auto j = e;
if(dist > dist + w){
dist = dist + w;
que.push({dist,j});
}
}
}
if(dist == 0x3f3f3f3f)cout << -1;
else cout << dist;
}
插入数据修改小根堆的时间复杂度为 O(logn)，总的复杂度为O(mnlogn),稀疏图m可以看作n，最后的时间复杂度为O(nlog)。 当图是绸密图时,m比大n x阶，复杂度为(m^x nlogn),显然不如前者。
Bellmen_ford算法
bellman-ford算法对所有边进行(n-1)松弛操作，只要算法中没有负权回路，bellman-ford算法就能求出最短路。复杂度为O(nm)
该算法与dijkstra算法的思路非常相象，不同之处在于一个对点操作，一个对边操作。
void bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist = 0;
for(int i = 0;i < n - 1;i++){
memcpy(last,dist,sizeof dist);
for(int j = 0;j < m;j++){
auto e = edges;
dist = min(dist,last + e.c);
}
}
}
SPFA
仔细看一看bellman-ford算法我们就会发现，在循环当中，有很多边根本不会被更新，只有与一条边相邻的边被更新之后，这条边才会被更新，这提醒我们可以使用queue对算法进行优化。
int spfa(){
queue<int> que;
que.push(1);
dist = 0;
st = true;
while(!que.empty()){
auto curr = que.front();
que.pop();
st = false;
for(int i = h;i != -1;i = ne){
auto j = e;
if(dist > dist + w){
dist = dist + w;
if(!st){
que.push(j);
st = true;
}
}
}
}
return dist;
}
一般情况下复杂度为O(m),不过可以构造出一些特殊的数据，使得最坏复杂度为O(nm)
多源最短路
Floyd算法
每次选一个点k做中间结点，对于两点，尝试i-k-j时候比i-j要小。
void floyd(){
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
d = min(d,d+d);
}
}
}
}
Reference:
页:
[1]