关于数据结构的选择:
视图的稀疏程度选择邻接表or邻接矩阵
前置问题 - BFS
首先将问题分为两类
第一类为单源最短路径问题
某些单源最短路径问题可能包括权重为负值的边,但如果图G=(V,E)不包含从远点S可以到达的权重为负值的环路,则对于所有节点v∈V,最短路径权重都有精确定义,即使取值为负数。反之则最短路径权重无定义。因为我们只要沿着任何“最短”路径再遍历一次权重为负的环路(negative-cost-cycle),总是可以找到一条权重更小的路径。
Dijkstra算法假设输入图的所有边的权重为非负值,而Bellman-Ford允许负值,只要没有可以从S到达的权重为负值的环路。如果存在,Bellman-Ford可以侦测并报告。
松弛操作(relaxation)
对于每个节点v来说,我们维持一个属性v.d,用来记录从源节点s到结点v的最短路径权重的上界。我们称v.d为s到v的最短路径估计。
我们可以利用INITIALIZE进行:
s.d=0
for each vertex in V - {s}:
v.d = ∞
对一条边的松弛过程为:
Relax(u,v,w)
if u.d > u.d + w(u, v)
v.d = u.d + w(u, v)
并更新path
1.Bellman-ford
Step:
- 1.INITIALIZE,将除源点外所有顶点的最短距离估计值dist[v] = infinity , dist[s] = 0
- 2.RELAX,对每条边进行松弛操作,渐近的降低从源结点s到每个结点v的最短路径估计值v.d (每条边执行|V|-1次)
-
3.检验negative-cost-cycle,判断边集E中的每条边的两个端点是否收敛,存在未收敛的顶点,返回FALSE
该算法返回TRUE当且仅当输入图不包含可以从源节点到达的权重为负值的环路。
void INITIAL_SINGLE_SOURCE()
{
for(int i=1; i<=node_num;++i){
if(i==s)
dist[i] = 0;
else
dist[i] = INFINITY;
}
}
int Bellman_Ford(Edge* edge)
{
INITIAL_SINGLE_SOURCE();
for(int i=1; i<= node_num - 1; ++i)
for(int j=1; j<= edge_num; ++j){
if(dist[edge[j].v] > dist[edge[j].u] + edge[j].w) //松弛
{
dist[edge[j].v] = dist[edge[j].u] + edge[j].w;
pre[edge[j].v] = edge[j].u;
}
}
int flag = 1;
for(int i = 1; i<=edge_num; ++i){
if(dist[edge[i].v] > dist[edge[i].u] + edge[i].w){
flag = 0;
break;
}
}
return flag;
}
void print_path(int root)
{
while(root != pre[root]){
printf("%d-->",root);
root = pre[root];
}
if(root == pre[root])
printf("%d\n", root);
}
2.Dijkstra
虽然bellman-ford可以解决负权值问题,但其时间复杂度为O(VE),Dijkstra会比他快。
Dijkstra算法在运行过程中维持的关键信息是一组结点集合S,这是一种贪心思想,从源节点S到该集合中每个节点之间的最短路径已经被找到。算法重复从结点V-S中选择最短路径估计最小的结点u,将u加入到集合S,然后队所有从u发出的边进行松弛。
于是我们先写出Dijkstra的伪代码:
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) //1、初始化结点工作
2 S ← Ø
3 Q ← V[G] //2、插入结点操作
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //3、从最小队列中,抽取最小点工作
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //4、松弛操作。
第三步中,我们要构造一个最小优先队列,其实现方法比较如下
EXTRACT-MIN + RELAX
I、 简单方式: O(V*V + E*1)
II、 二叉/项堆: O(V*lgV + |E|*lgV)
源点可达:O(E*lgV)
稀疏图时,有E=O(V^2/lgV),
=> O(V^2)
III、斐波那契堆:O(V*lgV + E)
Vertex FindMinDist()
{
/*找到最小的V 用二叉堆或Fibonacci可降低O*/
Vertex MinV,V;
int MinDist = INFINITY;
for( V=1; V<=G->n; V++){
if(collected[V] == 0 && dist[V]<MinDist){
//如果V未被收入,且dist更小
MinDist = dist[V];
MinV = V;
}
}
if(MinDist < INFINITY)
return MinV;
else return ERROR;
}
int Dijkstra()
{
Vertex V,W;
INITIALIZE();//初始化操作
while(1){
V = FindMinDist();
if( V == ERROR )
break;
collected[V] = 1;
for(W=1;W<=G->n;W++){
if(collected[W] == 0 && G->graph[V][W]< INFINITY){
if(G->graph[V][W] < 0){
return ERROR;
}
if(dist[V] + G->graph[V][W] < dist[W]){
//松弛操作
dist[W] = dist[V] + G->graph[V][W];
Path[W] = V;
}
}
}
}
return FINISHED;
}
网友评论