7-2 Dijkstra算法（模板） (30分)
给一个n(1 ≤ n ≤ 2500) 个点 m(1 ≤ m ≤ 6200) 条边的无向图，求 s 到 t 的最短路。
输入格式:
第一行四个由空格隔开的整数 n、m、s、t。
之后的 m 行，每行三个正整数 si、ti、wi(1≤wi≤109)，表示一条从si 到 ti 长度为 wi 的边。
输出格式:
一个整数，表示从s 到t 的最短路径长度。数据保证至少存在一条道路。
输入样例:
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例:
7
注意:
两个顶点之间可能存在多条直接相连的道路。
思路
纵观此题，要注意的点有两个——一是两个顶点之间可能存在多条直接相连的道路；二是数据保证至少存在一条道路。这意味此图必是稠密图，每两个顶点之间都有一条及以上的道路。据此我们可以用矩阵来存储此图，不过与先前不同的是矩阵里的每个元素应是我们自己定义的一个类，但是此题只需算出最短路径，那么这题我们路径只需保留最短的即可。
程序框架设计
1.array矩阵表示图，num结点数量，edge边数，maxInt常量表示无穷大，distance矩阵记录各个点之间的最短距离，s起点，t终点
2.initialize方法初始化图
3.私有方法createEdge（int a,int b）方法 建立一条边，把最短的一条边记录
4.dijkstra()方法
5. findMinDistance(boolean[] collected) 返回未被收录顶点中dist最小者的下标
6.find(int t)输出打印到t点的最短距离
import java.util.*; public class Main { //一个常量100000001表示无穷大 final static int MaxInt=100000001; //节点个数 static int num=0; //边数 static int edge=0; //二维矩阵 static int[][] array; static int[] distance; static int[] path; //起点 static int s; //终点 static int t; //建图模块 public static void main(String[] args) { //初始化 initialize(); //调用dijkstra算法 Dijkstra(); //输出到t点的最短距离 find(t); } public static void initialize(){ //创建一个文本扫描器检测键盘输入 Scanner scanner=new Scanner(System.in); num=scanner.nextInt(); edge=scanner.nextInt(); s= scanner.nextInt(); t= scanner.nextInt(); //注意这个下标并不是结点值，下标减一才是！！！ array=new int[num][num]; //初始化图中值 for (int i=0;i<num;i++){ for (int j=0;j<num;j++){ array[i][j]=MaxInt; } } for (int i=0;i<edge;i++){ creatEdge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()); } //初始化path和distance数组 path=new int[num]; distance=new int[num]; } //建立一条边,把小的一条边存储 private static void creatEdge(int a,int b,int length){ if (array[a-1][b-1]>length){ array[a-1][b-1]=length; array[b-1][a-1]=length; } } private static boolean Dijkstra() { //记录该点是否访问过 boolean collected[]=new boolean[num]; /* 初始化：此处默认邻接矩阵中不存在的边用MaxInt表示 */ for ( int i=0; i<num; i++ ) { distance[i] = array[i][s-1]; if ( distance[i]<MaxInt ) path[i] = s-1; else path[i] = -1; collected[i] = false; } /* 先将起点收入集合 */ distance[s-1] = 0; collected[s-1] = true; while (true) { // temp = 未被收录顶点中dist最小者的下标 int temp= findMinDistance(collected ); if ( temp==-1 ) /* 若这样的temp不存在 */ break; /* 算法结束 */ collected[temp] = true; /* 收录temp */ for( int i=0; i<num; i++ ) /* 对图中的每个顶点i+1 */ /* 若i是temp的邻接点并且未被收录 */ if ( collected[i]==false && array[temp][i]<MaxInt ) { if (array[temp][i]<0 ) /* 若有负边 */ return false; /* 不能正确解决，返回错误标记 */ /* 若收录temp使得distance[i]变小 */ if ( distance[temp]+array[temp][i]< distance[i] ) { distance[i] = distance[temp]+array[temp][i]; /* 更新distance[i] */ path[i] = temp; /* 更新s到i的路径 */ } } } /* while结束*/ return true; /* 算法执行完毕，返回正确标记 */ } //返回未被收录顶点中dist最小者的下标 private static int findMinDistance(boolean[] collected){ int min =MaxInt; int iMin=-1; for (int i=0;i<num;i++){ if (min>distance[i]&&!collected[i]){ min=distance[i]; iMin=i; } } return iMin; } //输出打印到t点的最短距离 private static void find(int t){ System.out.println(distance[t-1]); } }
