使用迪杰斯特拉算法解决任意两点间的最短路径问题
package list; import java.util.Scanner; /** * 稍微修改迪杰斯特拉算法即可得出结论 * 思路:从该结点出发，依次向外探测，并与修正与当前生成路径的最短路径 * @author 哑元 * */ public class Test1 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n,m,s,e; System.out.println("n、m、s、e的信息"); n = scan.nextInt(); //顶点数 m = scan.nextInt(); //边数 s = scan.nextInt() - 1; //当前结点 e = scan.nextInt() - 1; //要去的结点 //定义一个数组，用来存放顶点 int total[] = new int[n]; //用来存放到每个结点的路径长度 int edges[][] = new int[n][n]; //初始化边表 for (int i = 0; i < edges.length; i++) { for (int j = 0; j < edges[i].length; j++) { edges[i][j] = 0; //0表示没有边 } } //输入边表信息 System.out.println("请输入边信息"); for (int i = 0; i < m; i++) { System.out.println("请输入(vi,vj)的下标"); int a = scan.nextInt() - 1; int b = scan.nextInt() - 1; edges[a][b] = 1; edges[b][a] = 1; } boolean isFinal[] = new boolean[n]; //是否已经求得该结点的最短路径 for (int i = 0; i < isFinal.length; i++) { isFinal[i] = false; total[i] = edges[s][i]; ///将所有与初始结点相关的结点存放到表中 } total[s] = 0; isFinal[s] = true; //先标记初始结点 for (int j = 0; j < n; j++) { if(j == s) continue; int v = 0; for (int i = 0; i < n; i++) { //从初始结点开始 if(!isFinal[i] && total[i] != 0){ //==1表示当前路是通的 v = i; } } isFinal[v] = true; //将找到最近的结点标记 for (int i = 0; i < n; i++) { //修正当前生成路径到其他结点的距距离 if(!isFinal[i] && edges[v][i] == 1){ total[i] = total[v] + edges[v][i]; } } } System.out.println("输出当前结点到其余各节点的最短路径长度："); for (int i = 0; i < n; i++) { System.out.println(total[i]); } if(total[e] != 0){ System.out.println("两点间的最短路径长度为：" + total[e]); }else{ System.out.println("你就在那里或者你永远也到不了那里"); } } }输入模式和输出模式 n、m、s、e的信息 5 4 1 5 请输入边信息 请输入(vi,vj)的下标 1 2 请输入(vi,vj)的下标 2 3 请输入(vi,vj)的下标 3 4 请输入(vi,vj)的下标 4 5 输出当前结点到其余各节点的最短路径长度： 0 1 2 3 4 两点间的最短路径长度为：4
