這里使用的是Dijkstra來計(jì)算最短路徑。事實(shí)上Dijkstra完成時(shí)，指定節(jié)點(diǎn)到所有節(jié)點(diǎn)的最小路徑均已求出。
算法簡(jiǎn)述如下：
準(zhǔn)備好兩個(gè)輔助性數(shù)據(jù)結(jié)構(gòu)：
1 ParentLength ： 用來記錄到當(dāng)前節(jié)點(diǎn)之前的父節(jié)點(diǎn)，與到當(dāng)前節(jié)點(diǎn)的最小路徑
2 Path： 記錄指定節(jié)點(diǎn)到所有節(jié)點(diǎn)的ParentLength。初始化時(shí)，所有的ParentLength的父節(jié)點(diǎn)都為指定的起始節(jié)點(diǎn)，長(zhǎng)度都是INFINITY，代表沒有聯(lián)通，距離無窮大。
Path的關(guān)鍵算法是adjust(from,to,length)，每當(dāng)發(fā)現(xiàn)一條新的，從一個(gè)已訪問的節(jié)點(diǎn)（from）到未訪問的節(jié)點(diǎn)（to）之間的新路徑時(shí)，Path則用其更新ParentLength列表，重新計(jì)算到那個(gè)未訪問節(jié)點(diǎn)（to）的最新距離：以前到from節(jié)點(diǎn)的距離＋新的距離，然后比較它與to節(jié)點(diǎn)對(duì)應(yīng)的ParentLength老的距離之間的長(zhǎng)度，如果新距離短，則將to節(jié)點(diǎn)對(duì)應(yīng)的ParentLength更新為長(zhǎng)度為新距離的，父節(jié)點(diǎn)為from；以此步驟保證Path總是保持當(dāng)前遍歷狀態(tài)下，到各個(gè)節(jié)點(diǎn)的最短路徑。
Path的另一個(gè)關(guān)鍵算法是getMin，它會(huì)返回到所有未訪問節(jié)點(diǎn)中，最短的路徑的那個(gè)節(jié)點(diǎn)。
圖使用鄰接矩陣法表示，關(guān)于鄰接矩陣可參見：Graph 圖－鄰接表法
Graph.path是最小路徑算法，工作方式如下：
根據(jù)指定的起始節(jié)點(diǎn)初始化返回值Path對(duì)象。
將指定的起始節(jié)點(diǎn)標(biāo)志為已訪問。并設(shè)置為當(dāng)前節(jié)點(diǎn)。
然后
1 找到當(dāng)前節(jié)點(diǎn)所有聯(lián)通的未知節(jié)點(diǎn)，和到這些路徑長(zhǎng)度，調(diào)用Path.adjust更新Path。
2 步驟 1 結(jié)束后，從調(diào)用Path.getMin獲得到所有未訪問節(jié)點(diǎn)中，最短的路徑的那個(gè)節(jié)點(diǎn)。標(biāo)志為訪問過，并作為當(dāng)前節(jié)點(diǎn)。
3 重復(fù) 步驟 1 步驟 2 n次（n為圖中的節(jié)點(diǎn)數(shù)量），算法結(jié)束。
代碼中的Path.print()為打印函數(shù)，為測(cè)試之用。
Path.main()提供簡(jiǎn)單測(cè)試。
1
class ParentLength 
{ //記載上一個(gè)節(jié)點(diǎn)與當(dāng)前最小路徑
2
private int parent; //上一個(gè)節(jié)點(diǎn)
3 private int length; //最小路徑長(zhǎng)度
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 { //存儲(chǔ)最小路徑
14 private ParentLength[] pls;
15 private Graph g; //確定指定位置的節(jié)點(diǎn)是否被訪問過和打印時(shí)使用
16 Path(int size, int start, Graph g) {
17 //初始化最小路徑數(shù)組，將所有最小路徑的起點(diǎn)都置為start，并將路徑長(zhǎng)度置為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 //根據(jù)新發(fā)現(xiàn)的路徑調(diào)整最小路徑
25 void adjust(int from, int to, int length) {
26 //根據(jù)上一個(gè)節(jié)點(diǎn)的路徑，計(jì)算出新的路徑長(zhǎng)度
27 int newLength = pls[from].length() != Graph.INFINITY?
28 pls[from].length() + length: length;
29 //如果到指定節(jié)點(diǎn)的新路徑長(zhǎng)度小于原來的最小路徑，則更新到該節(jié)點(diǎn)的最小路徑，和其父節(jié)點(diǎn)
30 if(newLength < pls[to].length()) pls[to] = new ParentLength(from,newLength);
31 }
32
33 int getMin() { //求得到當(dāng)前所有未訪問節(jié)點(diǎn)的最近的一個(gè)節(jié)點(diǎn)
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 { //頂點(diǎn),記載數(shù)據(jù)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); //整數(shù)的最大值，表示沒有路徑
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) { //添加頂點(diǎn)
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; //設(shè)置指定節(jié)點(diǎn)之間的有向路徑
88 }
89
90 /** *//**
91 * 在鄰接矩陣中，查找指定頂點(diǎn)的未訪問過鄰居頂點(diǎn)
92 * 如果從從起點(diǎn)到終點(diǎn)的邊存在，且沒有標(biāo)志為訪問，則返回終點(diǎn)下標(biāo)。
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(); //將其實(shí)節(jié)點(diǎn)標(biāo)志為訪問過
109 for(int n=1; n<length; n++) { //一共經(jīng)過n此迭代就可得到最終結(jié)果
110 int i = 0;
111 while((i = findNeighbor(index,i+1)) != -1) //尋找當(dāng)前節(jié)點(diǎn)的所有為訪問鄰居
112 result.adjust(index, i, adjMat[index][i]); //根據(jù)新路線調(diào)整最小路徑
113 index = result.getMin(); //將當(dāng)前節(jié)點(diǎn)更新為路徑表中為訪問的最近的那個(gè)節(jié)點(diǎn)
114 vertexs[index].visit(); //將當(dāng)前節(jié)點(diǎn)標(biāo)志為訪問過;
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 //添加節(jié)點(diǎn)
127 g.add('a');
128 g.add('b');
129 g.add('c');
130 g.add('d');
131 g.add('e');
132 //添加有向有權(quán)邊
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}