这里使用的是Dijkstra来计算最短路径。事实上Dijkstra完成时，指定节点到所有节点的最小路径均已求出。
算法简述如下：
准备好两个辅助性数据结构：
1 ParentLength ： 用来记录到当前节点之前的父节点，与到当前节点的最小路径
2 Path： 记录指定节点到所有节点的ParentLength。初始化时，所有的ParentLength的父节点都为指定的起始节点，长度都是INFINITY，代表没有联通，距离无穷大。
Path的关键算法是adjust(from,to,length)，每当发现一条新的，从一个已访问的节点（from）到未访问的节点（to）之间的新路径时，Path则用其更新ParentLength列表，重新计算到那个未访问节点（to）的最新距离：以前到from节点的距离＋新的距离，然后比较它与to节点对应的ParentLength老的距离之间的长度，如果新距离短，则将to节点对应的ParentLength更新为长度为新距离的，父节点为from；以此步骤保证Path总是保持当前遍历状态下，到各个节点的最短路径。
Path的另一个关键算法是getMin，它会返回到所有未访问节点中，最短的路径的那个节点。
图使用邻接矩阵法表示，关于邻接矩阵可参见：Graph 图－邻接表法
Graph.path是最小路径算法，工作方式如下：
根据指定的起始节点初始化返回值Path对象。
将指定的起始节点标志为已访问。并设置为当前节点。
然后
1 找到当前节点所有联通的未知节点，和到这些路径长度，调用Path.adjust更新Path。
2 步骤 1 结束后，从调用Path.getMin获得到所有未访问节点中，最短的路径的那个节点。标志为访问过，并作为当前节点。
3 重复 步骤 1 步骤 2 n次（n为图中的节点数量），算法结束。
代码中的Path.print()为打印函数，为测试之用。
Path.main()提供简单测试。
1
class 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}