算法设计与分析 4.5 单源最短路径

/**
第一个设置标记算法是由 Dijkstra 提出的。

DijkstraAlgorithm(带权简单图 digraph, 顶点 first) {
    for 所有顶点 v
        currDist(v) = 无穷大;
    currDist(first) = 0;
    toBeChecked = 所有顶点;
    while toBeChecked 非空 {
        v = toBeChecked 中 currDist(v) 最小的一个顶点;
        从 toBeChecked 中删除 v;
        for toBeChecked 中所有和 v 邻接的顶点 u {
            if currDist(u) > currDist(v) + weight(edge(vu))
                currDist(u) = currDist(v) + weight(edge(vu));
                predecessor(u) = v;
            }    //end if
        }    //end for
    }    //end while
}    //end algorithm

说明：
    Dijkstra算法的复杂性是 O(|v|^2)。它不是通用的，因为它不能处理有负权的图，原因在于当前距离从无穷大设置成一个数值之后的顶点将不再被检测。
*/

import java.util.Arrays;

public class Dijkstra {
 /**
  Dijkstra算法可以描述如下，其中输入的带权有向图是G = (V, E), V = {0, 1, .., n-1}。顶点V是源。
  a是一个二维数组，a[i][j]表示边(i, j)的权。当(i, j)不属于E，a[i][j]是一个大数。dist[i]表示当前从
  源到顶点i的最短特殊路径长度。

  @param v  in the source vertex 
  @param a  the weight matrix
  @param dist the path length 
  @param prev the preverse vertex in the path
 */
    public static void dijkstra(int v, int[][] a, int[] dist, int[] prev) {
  int n = dist.length;
  if (v < 0 || v >= n) {
      throw new IllegalArgumentException("v should between 0 inclusive and dist.length exclusive.");
  }
  boolean[] toBeChecked = new boolean[n];
  for (int i = 0; i < n; i++) {            //toBeChecked = 所有顶点;
      dist[i] = a[v][i];
   toBeChecked[i] = false;
  }
  dist[v] = 0;

  

  for (int i = 0; i < n; i++) {
      int temp = Integer.MAX_VALUE;
   int u = v;
   for (int j = 0; j < n; j++) {           //u = toBeChecked 中 currDist(u) 最小的一个顶点;
       if (!toBeChecked[j] && dist[j] < temp) {
           u = j;
     temp = dist[j];
       }
   }
   toBeChecked[u] = true;             //从 toBeChecked 中删除 u;  
   for (int j = 0; j < n; j++) {
       if (!toBeChecked[j] && j != u && a[u][j] < Integer.MAX_VALUE) {  //toBeChecked 中所有和 u 邻接的顶点 j
           int newdist = dist[u] + a[u][j];
     if (newdist < dist[j]) {
         dist[j] = newdist;
      prev[j] = u;
     }
       }
   }
  }
 }

 private static void test() {
  int[][] matrix = {{0, 10, Integer.MAX_VALUE, 30, 100}
   , {Integer.MAX_VALUE, 0, 50, Integer.MAX_VALUE, Integer.MAX_VALUE}
   , {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 10}
   , {Integer.MAX_VALUE, Integer.MAX_VALUE, 20, 0, 60}
   , {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
   };
  int v = 0;
  int[] dist = new int[matrix.length];
  int[] prev = new int[matrix.length];
  dijkstra(v, matrix, dist, prev);
  System.out.println(Arrays.toString(dist));
  System.out.println(Arrays.toString(prev));
 }
 public static void main(String[] args) {
  test();
 }
}

 

/**
二.第一个纠正标记算法是由 Lester Ford 设计的。
它在整个图处理完成之前不会永久性确定任何节点的最短距离。
它比 Dijkstra 算法功能更强，因为它可以处理带负权的图(但不能是有负环的图)。

labelCorrectingAlgorithm(带权简单图 digraph, 顶点 first) {
    for 所有顶点 v
        currDist(v) = 无穷大;
    currDist(first) = 0;
    toBeChecked = {first};
    while toBeChecked 非空 {
        v = toBeChecked中的一个顶点;
        从 toBeChecked 中删除 v;
        for 所有和 v 邻接的顶点 u {
            if currDist(u) > currDist(v) + weight(edge(vu)) {
                currDist(u) = currDist(v) + weight(edge(vu));
                predecessor(u) = v;
                如果 u 不属于 toBeChecked ，就把它添加进去;
            }    //end if
        }    //end for
    }    //end while
}    //end algorithm

说明：算法的具体实例效率要根据toBeChecked表使用的数据结构以及从这个表抽取元素和插入元素的操作来确定
**/
import java.util.*;

public class LabelCorrectingShortestPathAlgorithm {

 public static void labelCorrectingShortestPathAlgorithm(int first, int[][] matrix, int[] currDist, int[] predecessor) {
  int n = currDist.length;
  for (int i = 0; i < n; i++) {
      currDist[i] = Integer.MAX_VALUE;
  }
  currDist[first] = 0;
  List<Integer> toBeChecked = new LinkedList<Integer>();
  toBeChecked.add(first);
  while (!toBeChecked.isEmpty()) {
      int v = toBeChecked.get(0);
   toBeChecked.remove(0);
   for (int i = 0; i < n; i++) {
       if (i != v && matrix[v][i] < Integer.MAX_VALUE) {      //所有和v邻接的顶点i
           if (currDist[i] > currDist[v] + matrix[v][i]) {
               currDist[i] = currDist[v] + matrix[v][i];
      predecessor[i] = v;
      if (toBeChecked.indexOf(i) == -1) {        //如果i不在toBeChecked中，则把它加进去
          toBeChecked.add(i);
      }
           }
       }
   }
  }
 }

 private static void test() {
  int[][] matrix = {{0, 10, Integer.MAX_VALUE, 30, 100}
   , {Integer.MAX_VALUE, 0, 50, Integer.MAX_VALUE, Integer.MAX_VALUE}
   , {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 10}
   , {Integer.MAX_VALUE, Integer.MAX_VALUE, 20, 0, 60}
   , {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
   };
  int v = 0;
  int[] dist = new int[matrix.length];
  int[] prev = new int[matrix.length];
  labelCorrectingShortestPathAlgorithm(v, matrix, dist, prev);
  System.out.println(Arrays.toString(dist));
  System.out.println(Arrays.toString(prev));
 }
 public static void main(String[] args) {
  test();
 }
}