Dijkstra算法

这是一个按路径长度递增的次序产生最短路径的算法。

操作步骤

(1) 定义集合distance、prevs、visited；distance表示起点startIndex到该顶点的距离，prevs表示当前顶点到起点的最短路径的前驱顶点，visited表示已经访问过的顶点。

(2) 初始时，distance只有起点的邻接顶点到起点的距离；prevs只有邻接顶点的前驱顶点是起始顶点，visited中标记起始顶点为已访问。

(3) 从distance中选出”距离最短的顶点minVertex”，并将顶点minVertex加入到visited中。

(4) 更新distance中minVertex顶点的邻接顶点到起点startIndex的距离。之所以更新distance中顶点的距离，是由于上一步中确定了minVertex是求出最短路径的顶点，从而可以利用minVertex来更新其它顶点的距离。

(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

代码实现

以下图为例

图的最短路径 - 图1 Dijkstra算法代码如下

  1. public static void dijkstra(Graph graph, int startIndex) {
  2.   int size = graph.vertexs.length;
  3.   int[] distance = new int[size];
  4.   int[] prevs = new int[size];
  5.   boolean[] visited = new boolean[size];
  7.   for (int i = 0; i < size; i++) {
  8.     distance[i] = Integer.MAX_VALUE;
  9.   }
  11.   for (Edge edge : graph.getAdjEdge(startIndex)) {
  12.     distance[edge.index] = edge.weight;
  13.     prevs[edge.index] = startIndex;
  14.   }
  16.   visited[0] = true;
  18.   for (int i = 1; i < size; i++) {
  20.     int minVertex = getMinVertex(visited, distance);
  22.     visited[minVertex] = true;
  24.     for (Edge edge : graph.getAdjEdge(minVertex)) {
  25.       if (visited[edge.index]) {
  26.           continue;
  27.       }
  28.       int dist = distance[minVertex] + edge.weight;
  29.       if (dist < distance[edge.index]) {
  30.           distance[edge.index] = dist;
  31.           prevs[edge.index] = minVertex;
  32.       }
  33.     }
  34.   }
  35. }
  37. public static int getMinVertex(boolean[] visited, int[] distance) {
  38.   int minVertex = 0;
  39.   int dist = Integer.MAX_VALUE;
  40.   for (int i = 1; i < distance.length; i++) {
  41.       if (visited[i]) {
  42.           continue;
  43.       }
  44.       if (distance[i] < dist) {
  45.           dist = distance[i];
  46.           minVertex = i;
  47.       }
  48.   }
  49.   return minVertex;
  50. }

构建图和顶点

  1. public static void main(String[] args) {
  2.   Vertex[] vertexs = {
  3.           new Vertex("1"),
  4.           new Vertex("2"),
  5.           new Vertex("3"),
  6.           new Vertex("4"),
  7.           new Vertex("5"),
  8.           new Vertex("6"),
  9.           new Vertex("7")};
  11.   Graph graph = new Graph(vertexs);
  13.   graph.addEdge(0, 1, 3);
  14.   graph.addEdge(0, 2, 4);
  15.   graph.addEdge(0, 3, 5);
  17.   graph.addEdge(1, 0, 3);
  18.   graph.addEdge(1, 3, 6);
  19.   graph.addEdge(1, 4, 7);
  21.   graph.addEdge(2, 0, 4);
  22.   graph.addEdge(2, 3, 7);
  23.   graph.addEdge(2, 5, 9);
  25.   graph.addEdge(3, 0, 5);
  26.   graph.addEdge(3, 1, 6);
  27.   graph.addEdge(3, 2, 7);
  28.   graph.addEdge(3, 4, 9);
  29.   graph.addEdge(3, 6, 11);
  30.   graph.addEdge(3, 5, 10);
  32.   graph.addEdge(4, 1, 7);
  33.   graph.addEdge(4, 3, 9);
  34.   graph.addEdge(4, 6, 12);
  36.   graph.addEdge(5, 3, 10);
  37.   graph.addEdge(5, 6, 13);
  38.   graph.addEdge(5, 2, 9);
  40.   graph.addEdge(6, 4, 12);
  41.   graph.addEdge(6, 3, 11);
  42.   graph.addEdge(6, 5, 13);
  44.   dijkstra(graph, 0);
  46. }

Floyd算法

和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

基本思想

通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

假设图G中顶点个数为N，则需要对矩阵S进行N次更新。初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。 接下来开始，对矩阵S进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k]+a[k][j]”，则更新a[i][j]为”a[i][k]+a[k][j]”。更新N次之后，操作完成！

算法图解

图的最短路径 - 图2