迪杰斯特拉算法求无向图最短路径-java实现

import java.util.Scanner; public class zhongxing02 { static final int MX =1000; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[][] road =new int[][]{ {0, 1, MX, 6, MX}, {1, 0, 1, MX, MX}, {MX, 1, 0, 3, 2}, {6, MX, 3, 0, MX}, {MX, MX, 2, MX, 0} }; while (sc.hasNext()){ int n = 5; //节点数目 int bg =sc.nextInt(); int end =sc.nextInt(); System.out.println(djstla(road,5,bg-1,end-1)); //第一个点对应index为0，所以-1 } } /** * * @param road 路径矩阵 * @param n 节点数目 * @param b 起点index * @param e 终点index * @return */ public static int djstla(int[][] road, int n, int b, int e) { boolean[] visited = new boolean[n]; int[] distance = new int[n]; for (int i = 0; i < n; i++) { //维护两个数组，每次找下一个节点只在没有访问过的点中寻找 visited[i] = false; distance[i] = MX; } visited[b] = true; distance[b] = 0; int cur = b; //current point int nextP =-1; int times =0; while (cur!=e&&times<(n-1)) { //超过目标点数还没有找到就不用找了 int minL =Integer.MAX_VALUE; for (int j = 0; j < n ; j++) { //寻找下一个节点 if (visited[j]) continue; //每次找下一个节点只在没有访问过的点中寻找 if (distance[cur] + road[cur][j] < distance[j]) { distance[j] = distance[cur] + road[cur][j]; } if (distance[j]<minL){ minL =distance[j]; nextP =j; } } visited[nextP] = true; cur =nextP; times++; } return distance[e]==MX?-1:distance[e]; } }