可以用于有向图和无向图。用负数表示该有向路不通。在EditPlus上写的，所以就一个.java文件。
package Test;import java.util.TreeMap;import java.util.ArrayList;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;class Point {private int id;// 点的idprivate boolean flag = false;// 标志是否被遍历int sum;// 记录总的点个数private TreeMap<Integer, Integer> thisPointMap = new TreeMap<Integer, Integer>();// 该点到各点的距离。BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in));Point(int sum) { // 构造函数 带有顶点个数this.sum = sum;}public void setId(int id) {// 设置顶点idthis.id = id;}public int getId() {// 获得顶点idreturn this.id;}public void changeFlag() {// 修改访问状态。this.flag = true;}public boolean isVisit() {// 查看访问状态return flag;}public void setLenToOther()throws IOException{// 初始化改点到各顶点的距离。System.out.println("=======请输入顶点" + (this.id + 1) + "至其他各顶点的边距=======");for (int i = 0; i < sum; i++) {if (i == this.id)thisPointMap.put(this.id, 0);else {System.out.print("至 顶点" + (i + 1) + " 的距离 ：");boolean flag =true;int len = 0;while(flag){try {len = Integer.valueOf(bufr.readLine());flag = false;} catch (NumberFormatException e) {System.out.print("输入有误，请重新输入：");}};thisPointMap.put(i, len);}}}// 该点到顶尖id的 距离。public int lenToPointId(int id) {return thisPointMap.get(id);}}class Dijkstra {public static void main(String[] args)throws IOException {ArrayList<Point> point_arr = new ArrayList<Point>();// 存储点集合BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in));System.out.print("请输入顶点个数： ");int sum = 0;boolean flag =true;while(flag){try {sum = Integer.valueOf(bufr.readLine());flag = false;} catch (NumberFormatException e) {System.out.print("输入有误，请重新输入：");}};for (int i = 0; i < sum; i++) {// 初始化Point p = new Point(sum);p.setId(i);p.setLenToOther();point_arr.add(p);}System.out.print("请输入起始顶点 id ：");boolean flag2 =true;int start = 0;while(flag2){try {start = Integer.valueOf(bufr.readLine())-1;if(start > sum-1 || start < 0)throw new NumberFormatException();flag2 = false;}catch (NumberFormatException e) {System.out.print("输入有误，请重新输入：");}};showDijkstra(point_arr, start);// 单源最短路径遍历}public static void showDijkstra(ArrayList<Point> arr, int i) {System.out.print("顶点" + (i + 1));arr.get(i).changeFlag();Point p1 = getTopointMin(arr, arr.get(i));if (p1 == null)return;int id = p1.getId();showDijkstra(arr, id);}public static Point getTopointMin(ArrayList<Point> arr, Point p) {Point temp = null;int minLen = Integer.MAX_VALUE;for (int i = 0; i < arr.size(); i++) {// 当已访问 或 者是自身或者无该路径时跳过。if (arr.get(i).isVisit() || arr.get(i).getId() == p.getId() || p.lenToPointId(i) < 0)continue;else {if (p.lenToPointId(i) < minLen) {minLen = p.lenToPointId(i);temp = arr.get(i);}}}if (temp == null)return temp;elseSystem.out.print(" @--" + minLen + "--> ");return temp;}}
运行结果：
请输入顶点个数： 5=======请输入顶点1至其他各顶点的边距=======至 顶点2 的距离 ：15至 顶点3 的距离 ：24至 顶点4 的距离 ：33至 顶点5 的距离 ：28=======请输入顶点2至其他各顶点的边距=======至 顶点1 的距离 ：16至 顶点3 的距离 ：25至 顶点4 的距离 ：18至 顶点5 的距离 ：21=======请输入顶点3至其他各顶点的边距=======至 顶点1 的距离 ：29至 顶点2 的距离 ：30至 顶点4 的距离 ：25至 顶点5 的距离 ：29=======请输入顶点4至其他各顶点的边距=======至 顶点1 的距离 ：31至 顶点2 的距离 ：36至 顶点3 的距离 ：22至 顶点5 的距离 ：11=======请输入顶点5至其他各顶点的边距=======至 顶点1 的距离 ：-1至 顶点2 的距离 ：-1至 顶点3 的距离 ：30至 顶点4 的距离 ：39顶点1 @--15--> 顶点2 @--18--> 顶点4 @--11--> 顶点5 @--30--> 顶点3
