這里使用的是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}