单源最短路径 Bellman_ford 和 dijkstra

时间:2022-11-21 22:39:48

首先两个算法都是常用于 求单源最短路径

关键部分就在于松弛操作 实际上就是dp的感觉

if (dist[e.to] > dist[v] + e.cost)

{

  dist[e.to] = dist[v] + e.cost;  

  ...

}

bellman_ford O(E*V) 但是配合队列可以 有spfa 可以达到O(kE)

http://www.360doc.com/content/13/1208/22/14357424_335569176.shtml

并且bellman_ford还适用于负边 并且可以利用最多循环V-1次的性质 判断是否存在负圈(如果循环超过V-1次 说明有负圈 因为没重复走着负圈一次 都伴随着更新)

并且因为松弛操作是针对于每条边的遍历也可以用向前星存

 #include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#define MAXV 10007
#define MAXE 1007
#define INF 0x3f3f3f3f
using namespace std; int V, E; struct Edge
{
int from, to, cost;
}edge[MAXE]; int bellman_ford(int s, int d)//求单源最短路径
{
int dist[MAXV];
fill (dist, dist+V+, INF);
dist[s] = ;
while (true)//直至update不在更新
{
bool update = false;
for (int i = ; i < E; i++)
{
if (dist[edge[i].from] != INF && dist[edge[i].to] > dist[edge[i].from] + edge[i].cost)
{
dist[edge[i].to] = dist[edge[i].from] + edge[i].cost;
update = true;
}
}
if (!update) break;
}
return dist[d];
}
//while(true) 循环中最多循环V-1次 复杂度是O(V*E)
//如果存在 从s可达的负圈 那么在第V次循环时也会更新 可以用这个性质来检查负圈
//如果一开始把dist都初始化为0 那么可以检查出所有的负圈
//检查负边 是负边 返回true
//P.S 圈表示基本回路
bool isNegtive()
{
int dist[MAXV];
memset(dist, , sizeof(dist));//单纯查负圈
for (int i = ; i < V; i++)
{
for (int i = ; i < E; i++)
{
Edge e = edge[i];
if (dist[e.to] < dist[e.from] + e.cost )
{
dist[e.to] = dist[e.from] + e.cost;
if (i == V-)//如果第V次还更新 那么就有负圈
return true;
}
}
}
return false;
}
int main()
{
ifstream cin ("in.txt");
cin >> V >> E;
for (int i = ; i < E; i++)
{
cin >> edge[i].from >> edge[i].to >> edge[i].cost;
}
cout << bellman_ford(, ) << endl;
}

dijkstra 普通写法O(V^2)

但是 dijkstra的特点 --->>是针对每一个点 通过它所对应的边更新 e.to的节点

每次取出的是离原点sorce 最近的点 所以就可以使用优先队列 那么就变成O(V*logV)

并且因为“是针对每一个点 通过它所对应的边更新 e.to的节点 ” 那么也很好试用向前星

 #include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <queue>
#define MAXV 10007
#define MAXE 1007
#define INF 0x3f3f3f3f
using namespace std; int V, E;
//迪杰特斯拉好像不是很好用向前星
//这个算法是针对每一个点更新 而向前星存储的是边的信息 要查找点就比较复杂 //用邻接矩阵存储 O(V^2)的算法 int cost[MAXV][MAXV];
int dijkstra(int s, int d)
{
int dist[MAXV];
bool use[MAXV];
fill(dist, dist+MAXV, INF);
memset(use, false, sizeof(use));
dist[s] = ;
while (true)
{
int v = -;
for (int i = ; i <= V; i++)//找一个最近的 未使用过的点
{
if (!use[i] && (v == - || dist[i] < dist[v])) v = i;
}
if (v == -) break;
use[v] = true;
for (int i = ; i <= V; i++)
{
dist[i] = min(dist[i], dist[v] + cost[v][i]);
}
}
return dist[d];
} //使用优先队列(也就是heap优化)O(E*logV)
//针对边来dp 这里可以用向前星存储了
struct Edge
{
int to, n, next;
}edge[MAXE];
int num = ;
int head[MAXV];
void Add(int from, int to, int c)
{
edge[num].n = c;
edge[num].to = to;
edge[num].next = head[from];//从头插入
head[from] = num++;
}
void init()//初始化
{
ifstream cin("in.txt");
memset(edge, -, sizeof(edge));
memset(head, -, sizeof(head));
cin >> V >> E;
for (int j = ; j < E; j++)
{
int from , to , c;
cin >> from >> to >> c;
Add(from, to, c);
}
} typedef pair<int, int> P;//first 表示与s的距离, second表示点的编号
int pre[MAXV];//记录前驱节点 在每次dist[j] = dist[k] + cost[k][j]更新时记录在到j的最短路径上的前驱节点就是k
int fast_dijkstra(int s, int d)
{
int dist[MAXV];
priority_queue<P, vector<P>, greater<P> > que;//用优先队列存储点的信息 每次弹出距离最短的点O(logV)
fill(dist, dist+MAXV, INF);
dist[s] = ;
que.push(P(, s));
while (!que.empty())
{
P p = que.top();
que.pop();
if (dist[p.second] < p.first) continue;
int t = head[p.second];
while (t != -)
{
Edge e = edge[t];
if (dist[e.to] > dist[p.second] + e.n)
{
dist[e.to] = dist[p.second] + e.n;
pre[e.to] = p.second;
que.push( P(dist[e.to], e.to) );
}
t = e.next;
}
}
return dist[d];
} int main()
{
/*
ifstream cin("in.txt");
cin >> V >> E;
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
cost[i][j] = INF;//不存在时 cost为INF
for (int j = 0; j < E; j++)
{
int from , to , c;
cin >> from >> to >> c;
cost[from][to] = c;
}
int ans = dijkstra(1, 7);
*/
init();
int ans = fast_dijkstra(,);
cout << ans << endl;
//这样路径即还原了
int t = pre[];
cout << << " ";
while(t != )
{
cout << t << " ";
t = pre[t];
}
cout << <<endl;
}