迪杰斯特拉算法

迪杰斯特拉(Dijkstra)算法是典型**最短路径算法**，用于计算一个结点到其它结点的最短路径。它的主要特点是以起始点为中心向外扩展(利用广度优先搜索思想)，直到扩展到终点。

迪杰斯特拉(Dijkstra)算法最佳应用-最短路径

1. 战争时期，胜利乡有7个村庄(A,B,C,D,E,F,G),现在又六个邮差，从G点出发，需要分别把邮件送到A,B,C,D,E,F六个村庄
2. 各个村庄的距离用边线表示(权)，比如A-B距离5公里
3. 问：如何计算出G村庄到其它各个村庄的最短距离？

• 思路分析
  • 从G开始，初始化三个数组：final[]表示该顶点是否已经访问过；dist[]表示G点到其它各点之间的最短路径长度;path[]表示路径上的前驱
  • 从G点(下标为6)开始，令其final[6]=true,dist[6]=0,path[6]=-1；其余顶点final[k]=false,disk[k]=arcs[6][k],path[k]=(arcs[6][k]==特定值) ? -1:6（其中arcs[u][v]代表从u顶点到v顶点的边线，这里用特定值表示不存在G顶点到某一顶点的路径）
  • n-1轮处理：循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点vi，令final[i]=true。并检查所有邻接自vi的顶点vj，如果final[j]=false并且dist[i]+arcs[i][j]<dist[j]，则令其dist[j]=dist[i]+arcs[i][j],path[j]=i
• 代码实现

import java.util.Arrays;public class DijkstraDemo {private static final int INF = Integer.MAX_VALUE;public static void main(String[] args) {char[] vertexes = {'A','B','C','D','E','F','G'};int[][] matrix = {{0,5,7,INF,INF,INF,2},{5,0,INF,9,INF,INF,3},{7,INF,0,INF,8,INF,INF},{INF,9,INF,0,INF,4,INF},{INF,INF,8,INF,0,5,4},{INF,INF,INF,4,5,0,6},{2,3,INF,INF,4,6,0}};Graph graph = new Graph(vertexes, matrix);Dijkstra dijkstra = new Dijkstra(vertexes.length);dijkstra.dijkstra(graph, 6);dijkstra.show(vertexes);}
}
class Dijkstra {// 是否找到最短路径private boolean[] finalArr;// 从某一个顶点出发到其它顶点的最短路径private int[] dist;// 找前驱，如果-1表示没有前驱private final int[] path;private static final int INF = Integer.MAX_VALUE;/*** @param vertexNum*/public Dijkstra(int vertexNum) {finalArr = new boolean[vertexNum];dist = new int[vertexNum];// 用最大值表示没有路径Arrays.fill(dist,INF);path = new int[vertexNum];Arrays.fill(path,-1);}/*** 迪杰斯特拉算法* @param graph 图相关数据* @param start 从哪一个顶点开始*/public void dijkstra(Graph graph,int start) {// 对初始顶点进行初始化finalArr[start] = true;dist[start] = 0;path[start] = -1;char[] vertexes = graph.getVertexes();int[][] edges = graph.getEdges();int length = vertexes.length;// 初始化除初始顶点之外的其它顶点for (int i = 0; i < length; i++) {if (start != i) {dist[i] = edges[start][i];path[i] = dist[i] == INF?-1:start;}}// 进行n-1论循环for (int i = 0; i < length - 1; i++) {// 每次挑选出没有确定最短路径的顶点之后更新顶点集的最短距离int min = INF;int minIndex = -1;for (int j = 0; j < length; j++) {if (!finalArr[j] && dist[j] < min) {min = dist[j];minIndex = j;}}// 确定最小路径finalArr[minIndex] = true;// 确定是否存在到其它未确定最短路径的顶点for (int j = 0; j < length; j++) {if (!finalArr[j] && edges[minIndex][j] != INF && (dist[minIndex] + edges[minIndex][j] < dist[j])) {dist[j] = dist[minIndex] + edges[minIndex][j];path[j] = minIndex;}}}}public void show(char[] vertexes) {int len = vertexes.length;for(int i = 0; i < len;i++) {System.out.println("到顶点" + vertexes[i] + "的最短路径为" + dist[i]);int p = path[i];System.out.print("存在的路径是：");System.out.print(vertexes[i] + "<-");while(p != -1) {System.out.print(vertexes[p] + "<-");p = path[p];}System.out.println();}}
}
class Graph {// 顶点集private char[] vertexes;// 邻接矩阵private int[][] edges;public Graph(char[] vertexes, int[][] edges) {int length = vertexes.length;this.vertexes = new char[length];this.edges = new int[length][length];// 初始化顶点集和邻接矩阵for (int i = 0; i < length; i++) {this.vertexes[i] = vertexes[i];}for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {this.edges[i][j] = edges[i][j];}}}public char[] getVertexes() {return vertexes;}public int[][] getEdges() {return edges;}
}