1 public class Dijsktra { 2 3 public static void main(String[] args) 4 { 5 Dijsktra d=new Dijsktra(); 6 int[][] w={{0,1},{2,0}}; 7 8 int[] a=d.DijsktraWay(w,0); 9 //System.out.println(1111); 10 } 11 12 // 返回来的是路径 13 public int[] DijsktraWay(int[][] weight, int start) { 14 15 // 接受一个有向图的权重矩阵�和一个起点编号start�从0编号�顶点存在数组中� 16 // 返回一个int[] 数组�表示从start到它的最短路径长度 17 int n = weight.length; // 顶点个数 18 19 int[] shortPath = new int[n]; // 存放从start到其他各点的最短路径 20 String[] path = new String[n]; // 存放从start到其他各点的最短路径的字符串表示 21 for (int i = 0; i < n; i++) { 22 path[i] = new String(start + ">" + i); 23 shortPath[i] = Integer.MAX_VALUE / 2; 24 } 25 int[] visited = new int[n]; // 标记当前该顶点的最短路径是否已经求出,1表示已求出 26 // 初始化�第一个顶点求出 27 shortPath[start] = 0;//没有环 28 visited[start] = 1; // 表示已经访问过 29 30 for (int count = 1; count <= n - 1; count++) // 要加入n-1个顶点，每次加入一个点后 31 //就会有一个点被标记 32 { 33 int k = -1; // 选出一个距离初始顶点start最近的未标记顶点 34 int dmin = Integer.MAX_VALUE / 2; 35 for (int i = 0; i < n; i++) { 36 //如果此点未访问并且距离起始点距离较上一个的小，则应进行修改 37 if (visited[i] == 0 && weight[start][i] < dmin) { 38 dmin = weight[start][i];//表示距离起始点最近的点 39 k = i;//将距离起始点最近的点标记为k 40 } 41 } 42 43 if (k == -1) { 44 break; 45 // return null; 46 } 47 // 将新选出的顶点标记为已求出最短路径�且到start的最短路径就是dmin 48 shortPath[k] = dmin; 49 visited[k] = 1; 50 // 以k为中间点�修正从start到未访问各点的距离 51 for (int i = 0; i < n; i++) { 52 if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) { 53 weight[start][i] = weight[start][k] + weight[k][i]; 54 path[i] = path[k] + ">" + i; 55 } 56 //System.out.println(shortPath[i]); 57 System.out.println( path[i]); 58 } 59 } 60 61 62 return shortPath; 63 } 64 65 }
确定起点的最短路径问题：即已知起始结点，求最短路径的问题。适合迪杰斯特拉算法。
确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径反转的确定起点的问题。