最短路径算法

jopen 8年前

单源最短路径问题

问题描述:给你一个顶点做源点,你想要知道,如何从源点到达其他所有点的最短路径。

OK,这个问题看起来没什么用。我们一般想知道的是A点到B点的最短路径,这个单源最短路径问题告诉我们A点到所有点的最短路径,会不会计算过多了呢?

有趣的是,解决A点到B点的最短路径算法不会比单源最短路径问题简单,我们所知的求A点到B点的最短路径算法就是求A点到任何点的最短路径。我们除了这样做,好像也没什么好办法了。

Dijkstra算法

基本原理:

每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。

适用条件与限制:

  • 有向图无向图都可以使用本算法,无向图中的每条边可以看成相反的两条边。
  • 用来求最短路的图中不能存在负权边。(可以利用拓扑排序检测)

算法流程:

在以下说明中,s为源,w[u,v]为点u和v之间的边的长度,结果保存在dist[]

  1. 初始化:源的距离dist[s]设为0,其他的点距离设为正无穷大,同时把所有的点的状态设为没有扩展过。
  2. 循环n-1次:
    1. 在没有扩展过的点中取距离最小的点u,并将其状态设为已扩展。
    2. 对于每个与u相邻(有向图只kao虑出度)的点v,执行Relax(u,v),也就是说,如果dist[u]+w[u,v]<dist[v],那么把dist[v]更新成更短的距离dist[u]+w[u,v]。此时到点v的最短路径上,前一个节点即为u。
    </li>
  3. 结束。此时对于任意的u,dist[u]就是s到u的距离。
  4. </ol>

    执行动画过程如下图:

    实例:

    用Dijkstra算法找出以A为起点的单源最短路径步骤如下

    代码:

    我们在OJ上完成这个算法:http://acm.hdu.edu.cn/showproblem.php?pid=1874

    import java.io.BufferedReader;  import java.io.IOException;  import java.io.InputStreamReader;  import java.io.StreamTokenizer;    public class Main  {   static int[][] v = new int[201][201];   static int[] dist = new int[201];   static boolean[] visit = new boolean[201];     public static void main(String[] args) throws IOException   {    StreamTokenizer in = new StreamTokenizer(new BufferedReader(      new InputStreamReader(System.in)));    int n, m, begin, end;    while (in.nextToken() != StreamTokenizer.TT_EOF)    {     n = (int) in.nval;     in.nextToken();     m = (int) in.nval;     init(n);     for (int i = 0; i < m; i++)     {      in.nextToken();      int a = (int) in.nval;      in.nextToken();      int b = (int) in.nval;      in.nextToken();      int d = (int) in.nval;      if (d < v[a][b])      {       v[a][b] = d;       v[b][a] = d;      }     }     in.nextToken();     begin = (int) in.nval;     in.nextToken();     end = (int) in.nval;     if (begin == end)     {      System.out.println("0");      continue;     }     dist[begin] = 0;     visit[begin] = true;     dijkstra(begin, n);     if (!visit[end])     {      System.out.println("-1");     }     else     {      System.out.println(dist[end]);     }    }   }     public static void init(int n)   {    for (int i = 0; i < n; i++)    {     visit[i] = false;     for (int j = 0; j < n; j++)     {      v[i][j] = 10000;     }    }   }     public static void dijkstra(int s, int n)   {    for (int i = 0; i < n; i++)    {     dist[i] = v[s][i];    }    for (int i = 0; i < n - 1; i++)    {     int min = 10000;     int index = 0;     for (int j = 0; j < n; j++)     {      if (!visit[j] && dist[j] < min)      {       min = dist[j];       index = j;      }     }     visit[index] = true;     for (int j = 0; j < n; j++)     {      if (!visit[j] && dist[index] + v[index][j] < dist[j])      {       dist[j] = dist[index] + v[index][j];      }     }    }   }  }
    可以看出时间复杂度为 O(v^2)。有没有更快的方法呢?

    由于每次都要找到未访问的点中距离最小的点,我们使用优先队列来解决这个问题,关于优先队列请查看这篇Blog。以下是利用优先队列实现的算法

    public static void dijkstrapq(int s, int n)   {    class Item implements Comparable<Item>    {     public int idx;     public int weight;       public Item(int idx, int weight)     {      this.idx = idx;      this.weight = weight;     }       @Override     public int compareTo(Item item)     {      if (this.weight == item.weight)      {       return 0;      }      else if (this.weight < item.weight)      {       return -1;      }      else      {       return 1;      }     }    }    PriorityQueue<Item> pq = new PriorityQueue<Item>();    for (int i = 0; i < n; i++)    {     dist[i] = v[s][i];     if (i != s)     {      pq.offer(new Item(i, dist[i]));     }    }    Item itm = null;    while (!pq.isEmpty())    {     itm = pq.poll();     int index = itm.idx;     int weight = itm.weight;     if (weight == 10000)     {      break;     }     visit[index] = true;     for (int j = 0; j < n; j++)     {      if (!visit[j] && dist[index] + v[index][j] < dist[j])      {       dist[j] = dist[index] + v[index][j];       pq.offer(new Item(j, dist[j]));      }     }    }   }
    如果是稠密图(边比点多),则直接扫描所有未收录顶点比较好,即第一种方法,每次O(V),总体算法复杂度T=O(V^2+E)

    如果是稀疏图(边比点少),则使用优先队列(最小堆)比较好,即第二种方法,每次O(logV),插入更新后的dist,O(logV)。总体算法复杂度T=O(VlogV+ElogE)

    当然还有更加优秀的斐波那契堆,时间复杂度为 O(e+vlogv)

    无权值(或者权值相等)的单源点最短路径问题,Dijkstra算法退化成BFS广度优先搜索。

    那么,为什么BFS会比Dijkstra在这类问题上表现得更加好呢?

    1. BFS使用FIFO的队列来代替Dijkstra中的优先队列(或者heap之类的)。

    2. BFS不需要在每次选取最小结点时判断其他结点是否有更优的路径。

    BFS的时间复杂度为O(v+e)

    Bellman-Ford算法

    Dijkstra很优秀,但是使用Dijkstra有一个最大的限制,就是不能有负权边。而Bellman-Ford适用于权值可以为负、无权值为负的回路的图。这比Dijkstra算法的使用范围要广。其基本思想为:首先假设源点到所有点的距离为无穷大,然后从任一顶点u出发,遍历其它所有顶点vi,计算从源点到其它顶点vi的距离与从vi到u的距离的和,如果比原来距离小,则更新,遍历完所有的顶点为止,即可求得源点到所有顶点的最短距离。

    Bellman-Ford算法可以大致分为三个部分

    • 第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。
    • 第二,进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
    • 第三,遍历途中所有的边(edge(u,v)),判断是否存在这样情况:d(v) > d (u) + w(u,v)。则返回false,表示途中存在从源点可达的权为负的回路。

    对有向带权图G = (V, E),从顶点s起始,利用Bellman-Ford算法求解各顶点最短距离,算法描述如下:

    for(int k=1;k<=n-1;k++)//遍历点的次数       {           for(int i=1;i<=m;i++)//遍历边的次数           {               if(dis[v[i]]>dis[u[i]]+w[i])//如果从u到v的距离能够通过w这条边压缩路径 就要进行松弛操作               {                   dis[v[i]]=dis[u[i]]+w[i];               }           }       }

    很明显Bellman-Ford算法复杂度为O(VE),比Dijkstra要慢,但是解决了负权值问题。

    图解:

    当然不用总是松弛E次,可能远小于E次时,所有边都不能松弛了。所以加个check来优化,如果每个边都没松弛,就break。

    for(int k=1;k<=n-1;k++)    {        check=0;//用check检查是否进行下一轮次的操作        for(int i=1;i<=m;i++)        {            if(dis[v[i]]>dis[u[i]]+w[i])            {                dis[v[i]]=dis[u[i]]+w[i];                check=1;            }        }        if(check==0)break;    }

     我们一直说的是有向图的松弛,如果是无向图则要松弛两次(因为A到B有边,那么B到A也有边)

    for(int k=1;k<=n-1;k++)    {        check=0;        for(int i=1;i<=m;i++)        {            if(dis[v[i]]>dis[u[i]]+w[i])            {                dis[v[i]]=dis[u[i]]+w[i];                check=1;            }            if(dis[u[i]]>dis[v[i]]+w[i])            {                dis[u[i]]=dis[v[i]]+w[i];                check=1;            }        }        if(check==0)break;    }

    代码:

    我们在OJ上验证这个算法:http://acm.hdu.edu.cn/showproblem.php?pid=2544

    import java.io.BufferedReader;  import java.io.IOException;  import java.io.InputStreamReader;  import java.io.StreamTokenizer;    public class Main  {   static int[] begin = new int[121212];   static int[] end = new int[121212];   static int[] wight = new int[121212];   static int[] dist = new int[121212];     public static void main(String[] args) throws IOException   {    StreamTokenizer in = new StreamTokenizer(new BufferedReader(      new InputStreamReader(System.in)));    int n, m;    while (in.nextToken() != StreamTokenizer.TT_EOF)    {     n = (int) in.nval;     in.nextToken();     m = (int) in.nval;     init(n);     if (n == 0 || m == 0)     {      break;     }     for (int i = 1; i <= m; i++)     {      in.nextToken();      int a = (int) in.nval;      in.nextToken();      int b = (int) in.nval;      in.nextToken();      int d = (int) in.nval;      begin[i] = a;      end[i] = b;      wight[i] = d;      if (a == 1)      {       dist[b] = d;      }      if (b == 1)      {       dist[a] = d;      }     }     bellmanFord(n, m);     System.out.println(dist[n]);    }   }     private static boolean bellmanFord(int n, int m)   {    dist[1] = 0;    int check;    for (int i = 1; i <= n - 1; i++)    {     check = 0;     for (int j = 1; j <= m; j++)     {      int b = begin[j];      int e = end[j];      if (dist[b] + wight[j] < dist[e])      {       check = 1;       dist[e] = wight[j] + dist[b];      }      if (dist[e] + wight[j] < dist[b])      {       check = 1;       dist[b] = wight[j] + dist[e];      }     }     if (check == 0)     {      break;     }    }    return true;   }     public static void init(int n)   {    for (int i = 1; i <= n; i++)    {     dist[i] = 9999999;    }   }    }
    OJ上的这个题目没有负值环,Bellman-Ford是可以检查负值环的,就如上面所说,最后再遍历一遍边,如果还能松弛,说明有负值环。
    for (int j = 1; j <= m; j++)  {         int b = begin[j];   int e = end[j];   if (dist[b] + wight[j] < dist[e])   {    return false;   }   if (dist[e] + wight[j] < dist[b])   {    return false;   }  }

    SPFA算法

    SPFA(Shortest Path Faster Algorithm)(队列优化)算法是求单源最短路径的一种算法,它还有一个重要的功能是判负环(在差分约束系统中会得以体现),在Bellman-ford算法的基础上加上一个队列优化,减少了冗余的松弛操作,是一种高效的最短路算法。

    SPFA算法维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。

    SPFA算法可以分为大致3步

    • 初始化阶段除了和Bellman-ford算法相同的地方外,还要加上将源点S入队,并且在判断点是否在队列中的数组上做标记(inside[1] = 1)
    • 进行迭代,每次迭代,取出队头的点v,遍历所有与v相连的边,进行松弛操作,如果能够松弛并且该点不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空。
    • 若一个点入队次数超过n,则有负权环。

    SPFA 在形式上和宽度优先搜索非常类似,不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进,于是再次用来改进其它的点,这样反复迭代下去。

    代码:

    我们在OJ上验证这个算法:http://acm.hdu.edu.cn/showproblem.php?pid=2544

    import java.io.BufferedReader;  import java.io.IOException;  import java.io.InputStreamReader;  import java.io.StreamTokenizer;  import java.util.LinkedList;  import java.util.Queue;    public class Main  {   static int[][] v = new int[101][101];   static int[] dist = new int[101];   static int[] inside = new int[101];   static Queue<Integer> queue;     public static void main(String[] args) throws IOException   {    StreamTokenizer in = new StreamTokenizer(new BufferedReader(      new InputStreamReader(System.in)));    int n, m;    while (in.nextToken() != StreamTokenizer.TT_EOF)    {     n = (int) in.nval;     in.nextToken();     m = (int) in.nval;     init(n);     if (n == 0 || m == 0)     {      break;     }     for (int i = 1; i <= m; i++)     {      in.nextToken();      int a = (int) in.nval;      in.nextToken();      int b = (int) in.nval;      in.nextToken();      int d = (int) in.nval;      v[a][b] = d;      v[b][a] = d;     }     SPFA(n);     System.out.println(dist[n]);    }   }     private static void SPFA(int n)   {    queue.add(1);    inside[1] = 1;    dist[1] = 0;    while (!queue.isEmpty())    {     int top = queue.poll();     inside[top] = 0;     for (int i = 1; i <= n; i++)     {      if (v[top][i] < 9999999)      {       if (dist[top] + v[top][i] < dist[i])       {        dist[i] = dist[top] + v[top][i];        if (inside[i] == 0)        {         queue.add(i);         inside[i] = 1;        }       }      }     }    }   }     public static void init(int n)   {    for (int i = 1; i <= n; i++)    {     dist[i] = 9999999;     inside[i] = 0;     for (int j = 1; j <= n; j++)     {      v[i][j] = 9999999;     }    }    queue = new LinkedList<Integer>();   }    }
    由于上述代码使用邻接矩阵来存储,所以在遍历与某点相连的边时,复杂度较高。如果将其改成邻接表来实现会更加明显。

    在平均情况下,SPFA算法的期望时间复杂度为O(E)。但是这一说法有争议,在这里就不讨论了,总之SPFA是一种Bellman-Ford算法的优化。

    多源最短路径问题

    我们已经介绍了3种解决单源最短路径问题的算法,

    那么多源最短路径问题该怎么解决呢?

    很明显有一种方法就是,将单源最短路径问题使用N次,那么使用普通的Dijkstra算法的时间复杂度为T=O(V^3+V*E),对于稀疏图的效果比较好。

    而第二种方法则是要介绍的Floyd算法,它的时间复杂度为T=O(V^3),对于稠密图来说效果更好。

    Floyd算法

    对于最短路径算法来说,其重点都是松弛。由于现在是多源最短路径问题,以前单源把dist[i]作为源点S到i的最短路径,现在源点不单一了,所以直接表示成e(i,j)表示i到j的最短路径。

    我们已经知道松弛的原因是,有了第三个点为过渡点,使得距离变小了。

    Floyd算法运用动态规划的思想通过考虑最佳子路径来得到最佳路径

    Floyd算法的步骤就分为以下两步

    • 初始化:从任意一条单边路径开始。所有两点之间的距离是边的权,或者无穷大,如果两点之间没有边相连。
    • 松弛:对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

    思想非常简单,简单来说就是遍历所有的顶点,看看这个顶点是否能让任意两个顶点松弛。

    核心代码:

    for (int k = 1; k <= n; k++)    {     for (int i = 1; i <= n; i++)     {      for (int j = 1; j <= n; j++)      {         if (v[i][k] + v[k][j] < v[i][j])       {        v[i][j] = v[i][k] + v[k][j];       }        }     }    }

    代码:

    我们在OJ上验证这个算法:http://acm.hdu.edu.cn/showproblem.php?pid=2544

    import java.io.BufferedReader;  import java.io.IOException;  import java.io.InputStreamReader;  import java.io.StreamTokenizer;    public class Main  {   static int[][] v = new int[101][101];     public static void main(String[] args) throws IOException   {    StreamTokenizer in = new StreamTokenizer(new BufferedReader(      new InputStreamReader(System.in)));    int n, m;    while (in.nextToken() != StreamTokenizer.TT_EOF)    {     n = (int) in.nval;     in.nextToken();     m = (int) in.nval;     init(n);     if (n == 0 || m == 0)     {      break;     }     for (int i = 1; i <= m; i++)     {      in.nextToken();      int a = (int) in.nval;      in.nextToken();      int b = (int) in.nval;      in.nextToken();      int d = (int) in.nval;      v[a][b] = d;      v[b][a] = d;     }     floyd(n);     System.out.println(v[1][n]);    }   }     private static void floyd(int n)   {    for (int k = 1; k <= n; k++)    {     for (int i = 1; i <= n; i++)     {      for (int j = 1; j <= n; j++)      {         if (v[i][k] + v[k][j] < v[i][j])       {        v[i][j] = v[i][k] + v[k][j];       }        }     }    }   }     public static void init(int n)   {    for (int i = 1; i <= n; i++)    {     for (int j = 1; j <= n; j++)     {      v[i][j] = 9999999;     }    }   }    }
    算法时间复杂度很直观O(V^3),因为要用邻接矩阵来存储图,空间复杂度O(V^2)。

    另外需要注意的是:Floyd算法也不能解决带有“负权回路”

    总结:

    通过以上4种最短路径算法,我们发现,最短路径算法大概分为3步

    1. 初始化
    2. 松弛
    3. 判断是否有负值环

    其中Bellman-Ford(松弛以后如果还能松弛则有负值环)与SPFA(每个元素的入队次数不能超过n)能检测负值环。

    我们简单的说一下4种算法的松弛过程:

    1. Dijkstra:由源点出发,松弛每条边。然后选出其中最小的边,将其作为中间点,松弛其他未访问的边,如此循环n-1次。
    2. Bellman-Ford:遍历所有边,查看两个端点能否通过这条边进行松弛。
    3. SPFA:用队列来优化Bellman-Ford,从队列中取出某个点,查看经过这个点能否使边松弛,如果能够松弛并且没有在队列中,将另一个点加入队列中。
    4. Floyd:遍历所有的顶点,看看这个顶点是否能让任意两个顶点松弛。

    时间复杂度:

    Dijkstra:普通:O(V^2+E),最小堆优化:O(VlogV+ElogE),斐波那契堆优化:O(E+VlogV)

    Bellman-Ford:O(VE)

    SPFA:O(kE),有争论,总之比Bellman-Ford更加快

    Floyd:O(V^3)

    Reference:

    1. http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

    2. http://www.nocow.cn/index.php/Dijkstra%E7%AE%97%E6%B3%95

    3. http://blog.csdn.net/collonn/article/details/18155655

    4. http://blog.csdn.net/mengxiang000000/article/details/50266373

    来自: http://my.oschina.net/hosee/blog/602483