最短路径 bellmanford、dijkstra

2018-07-15 本文已影响0人 catttthrine

关于数据结构的选择：
视图的稀疏程度选择邻接表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;
  
}

最短路径 bellmanford、dijkstra

1.Bellman-ford

2.Dijkstra

猜你喜欢

热点阅读