1class ParentLength {    //记载上一个节点与当前最小路径
2    private int parent;        //上一个节点
3    private int length;        //最小路径长度
4    ParentLength(int parent, int length) {
5        this.parent = parent;
6        this.length = length;
7    }
8
9    int parent() {    return parent; }
10    int length() {    return length; }
11}
12
13class Path {    //存储最小路径
14    private ParentLength[] pls;
15    private Graph g;    //确定指定位置的节点是否被访问过和打印时使用
16    Path(int size, int start, Graph g) {
17        //初始化最小路径数组，将所有最小路径的起点都置为start，并将路径长度置为INFINITY
18        pls = new ParentLength[size];
19        for(int i=0; i<size; i++)
20            pls[i] = new ParentLength(start,Graph.INFINITY);
21        this.g = g;
22    }
23
24    //根据新发现的路径调整最小路径
25    void adjust(int from, int to, int length) {
26        //根据上一个节点的路径，计算出新的路径长度
27        int newLength = pls[from].length() != Graph.INFINITY?
28            pls[from].length() + length: length;
29        //如果到指定节点的新路径长度小于原来的最小路径，则更新到该节点的最小路径，和其父节点
30        if(newLength < pls[to].length()) pls[to] = new ParentLength(from,newLength);
31    }
32
33    int getMin() {    //求得到当前所有未访问节点的最近的一个节点
34        int pos = 0;
35        for(int i=1; i<pls.length; i++)
36            if(!g.isVisited(i) && pls[i].length() < pls[pos].length()) pos = i;
37        return pos;
38    }
39
40    void print() {    //打印
41        for(int i=0; i<pls.length; i++) {
42            int current = i;
43            System.out.print((pls[current].length() == Graph.INFINITY? ”INFINITY”: pls[current].length()) + ”  ” );
44            do {
45                System.out.print(g.get(current) + ” <– ”);
46                current = pls[current].parent();
47            } while(current != pls[current].parent());
48            System.out.println(g.get(current));
49        }
50    }
51}
52
53class Vertex { //顶点,记载数据value，并记载是否访问过
54    private Object value;
55    private boolean isVisited;
56    Vertex(Object value) {
57        this.value = value;
58    }
59
60    void visit() { isVisited = true; }
61    void clean() {    isVisited = false; }
62    boolean isVisited() { return isVisited; }
63    Object value() { return value; }
64    @Override public String toString() {    return ”" + value; }
65}
66
67class Graph {
68    private Vertex[] vertexs;
69    private int[][] adjMat;
70    private int length = 0;
71    static final int INFINITY = ~(1<<31);    //整数的最大值，表示没有路径
72
73    Graph(int size) {    //初始化
74        vertexs = new Vertex[size];
75        adjMat = new int[size][size];
76        for(int i=0; i<size; i++)    //将邻接矩阵初始化为全部不通
77            for(int j=0; j<size; j++)
78                adjMat[i][j] = INFINITY;
79    }
80
81    void add(Object value) {    //添加顶点
82        assert length <= vertexs.length;
83        vertexs[length++] = new Vertex(value);
84    }
85
86    void connect(int from, int to, int length) {
87        adjMat[from][to] = length;    //设置指定节点之间的有向路径
88    }
89
90    /**
91     * 在邻接矩阵中，查找指定顶点的未访问过邻居顶点
92     * 如果从从起点到终点的边存在，且没有标志为访问，则返回终点下标。
93     * @param offset 指定开始查找的列
94     * @param index    指定查找的行
95     */
96    int findNeighbor(int index,int offset) {
97        for(int i=offset; i<length; i++) {
98            if(adjMat[index][i] != INFINITY && !vertexs[i].isVisited()) return i;
99        }
100        return -1;
101    }
102
103    Vertex get(int index) {    return vertexs[index];    }
104
105    Path path(int index) {    //最小路径算法
106        assert vertexs[index] != null;
107        Path result = new Path(length,index,this); //初始化Path
108        vertexs[index].visit();    //将其实节点标志为访问过
109        for(int n=1; n<length; n++) {    //一共经过n此迭代就可得到最终结果
110            int i = 0;
111            while((i = findNeighbor(index,i+1)) != -1)    //寻找当前节点的所有为访问邻居
112                result.adjust(index, i, adjMat[index][i]);    //根据新路线调整最小路径
113            index = result.getMin();    //将当前节点更新为路径表中为访问的最近的那个节点
114            vertexs[index].visit();    //将当前节点标志为访问过;
115        }
116        clean();
117        return result;
118    }
119
120    boolean isVisited(int index) { return vertexs[index].isVisited(); }
121
122    void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }
123
124    public static void main(String[] args) {
125        Graph g = new Graph(20);
126        //添加节点
127        g.add(‘a’);
128        g.add(‘b’);
129        g.add(‘c’);
130        g.add(‘d’);
131        g.add(‘e’);
132        //添加有向有权边
133        g.connect(0,1,50);
134        g.connect(0,3,80);
135        g.connect(1,2,60);
136        g.connect(1,3,90);
137        g.connect(2,4,40);
138        g.connect(3,2,20);
139        g.connect(3,4,70);
140        g.connect(4,1,50);
141        Path p = g.path(0);    //获得最小路径
142        p.print();    //打印
143    }
144}