在一个图中，若从一个结点到另一个结点存在着路径，定义路径长度为一条路径上所经过的边的数目。图中从一个结点到另一个结点可能存在着多条路径，我们把路径长度最短的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离.
在一个带权图中，若从一个结点到另一个结点存在着一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中从一个结点到另一个结点可能存在着多条路径，我们把带权路径长度值最小的那条路径也叫做最短路径，其带权路径长度也叫做最短路径长度或最短距离。
8.6.2 从一个点到其余各结点的最点路径
1 狄克斯特拉算法思想
狄克斯特拉算法是：设置两个结点的集合S和T，集合S中存放已找到最短路径的结点，集合T中存放当前还未找到最短路径的结点。初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点v0路径长度最短的结点u加入到集合S中，集合S中每加入一个新的结点u都要修改源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各结点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过结点u到达该结点的路径长度中的较小者。此过程不断重复，直到集合T中的结点全部加入到集合S 中为止。 下图为意示例：
8.6.3 每对结点之间的最短路径
弗洛伊德算法是：设矩阵cost用来存放带权有向图G的权值，即矩阵元素cost[i][j]中存放着下标为i的结点到下标为j的结点之间的权值，可以通过递推构造一个矩阵序列A0,A1,A2,……,AN来求每对结点之间的最短路径。初始时有，A0[i][j]=cost[i][j]。当已经求出Ak,要递推求解Ak+1时，可分两种情况来考虑：一种情况是该路径不经过下标为k+1的结点，此时该路径长度与从结点vi到结点vj的路径上所经过的结点下标不大于k的最短路径长度相同；另一种情况是该路径经过下标为k+1的结点，此时该路径可分为两段，一段是从结点vi到结点vk+1的最短路径，另一段是从结点vk+1到结点vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况中的路径长度较小者，就是要求的从结点vi到结点vj的路径上所经过的结点下标不大于k+1的最短路径长度。
弗洛伊德算法的算法思想可用如下递推公式描述：
A0[i][j]=cost[i][j]
Ak+1[i][j]=min{Ak[i][j], Ak[i][k+1]+Ak[k+1][j]} （0≤k≤n-1）
也就是说，初始时，A0[i][j]=cost[i][j]，然后进行递推，每递推一次，从结点vi到结点vj的最短路径上就多考虑了一个经过的中间结点，这样，经过n次递推后得到的An[i][j]就是考虑了经过图中所有结点情况下的从结点vi到结点vj的最短路径长度。
package cn.ls.path;
import cn.ls.graph.AdjMWGraph;
/**
* 狄克斯特拉算法实现
* 最短路径.
*/
public class Dijkstra {
static final int maxWeight = 9999;
/**
*
* @param g 矩阵图类
* @param v0 源点序号
* @param distance 用来存放从源点v0到其余各结点的最短距离数值。
* @param path 用来存放从源点v0到其余各结点的最短距离上到达目标结点的前一结点下标。
* @throws Exception
*/
public static void dijkstra(AdjMWGraph g, int v0, int[] distance, int path[]) throws Exception {
int n = g.getNumOfVertices();
int[] s = new int[n]; //用来存放n个结点的标记.
int minDis, u = 0;
for (int i = 0; i < n; i++) {
distance[i] = g.getWeight(v0, i);
s[i] = 0; //初始标记为0
if (i != v0 && distance[i] < maxWeight)
path[i] = v0;
else
path[i] = -1;
}
s[v0] = 1; //标记结点v0已从集合T加入到集合S中.
//在还未找到最短路径的节点集中选取具有最短路径的结点U
for (int i = 1; i < n; i++) {
minDis = maxWeight;
for (int j = 0; j < n; j++){
if (s[j] == 0 && distance[j] < minDis) {
u = j;
minDis = distance[j];
}
}
//已不存在路径时算法结束, 对非连通图是必须的
if (minDis == maxWeight)
return;
s[u] = 1; //标记结点u已从集合T加入到集合S中.
//修正从v0到其他结点的最短距离和最短路径.
for (int j = 0; j < n; j++){
//例如由A-->B 原来距离为无穷大，现在则将距离变成20。此时Path[1] = 2.也就是到达B的前一结点的下标值是2(C).
if (s[j] == 0 && g.getWeight(u, j) < maxWeight && distance[u] + g.getWeight(u, j) < distance[j]) {
distance[j] = distance[u] + g.getWeight(u, j);
path[j] = u;
}
}
}
}
}
package cn.ls.graph;/** * *邻接矩阵图类 */public class AdjMWGraph { static final int maxWeight = 10000; private SeqList vertices; // 存储结点的顺序表 private int[][] edge; // 存储边的二维数组 private int numOfEdges; // 边的个数 public AdjMWGraph(int maxV) { // 构造函数，maxV为结点个数 vertices = new SeqList(maxV); edge = new int[maxV][maxV]; for (int i = 0; i < maxV; i++) { for (int j = 0; j < maxV; j++) { if (i == j) edge[i][j] = 0; else edge[i][j] = maxWeight; } } numOfEdges = 0; } public int getNumOfVertices() { // 返回结点个数 return vertices.size; } public int getNumOfEdges() { // 返回边的个数 return numOfEdges; } public Object getValue(int v) throws Exception { // 返回结点v的数据元素 return vertices.getData(v); } /** * 返回边<v1,v2>的权值 * @param v1 边的行下标 * @param v2 边的列下标 * @return * @throws Exception */ public int getWeight(int v1, int v2) throws Exception { if (v1 < 0 || v1 >= vertices.size || v2 < 0 || v2 >= vertices.size) throw new Exception("参数v1或v2越界出错！"); return edge[v1][v2]; } public void insertVertex(Object vertex) throws Exception { // 插入结点 vertices.insert(vertices.size, vertex); } /** * 插入边<v1,v2>，权值为weight * @param v1 边的行下标 * @param v2 边的列下标 * @param weight 边的权值 * @throws Exception */ public void insertEdge(int v1, int v2, int weight) throws Exception { if (v1 < 0 || v1 >= vertices.size || v2 < 0 || v2 >= vertices.size) throw new Exception("参数v1或v2越界出错！"); edge[v1][v2] = weight; //置边的权值 numOfEdges++; //边的个数加1 } public void deleteEdge(int v1, int v2) throws Exception { //删除边<v1,v2> if (v1 < 0 || v1 > vertices.size || v2 < 0 || v2 > vertices.size) throw new Exception("参数v1或v2越界出错！"); if (edge[v1][v2] == maxWeight || v1 == v2) throw new Exception("该边不存在！"); edge[v1][v2] = maxWeight; // 置边的权值为无穷大 numOfEdges--; // 边的个数减1 } public int getFirstNeighbor(int v) throws Exception { // 取结点v的第一个邻接结点。若存在返回该结点的下标序号，否则返回-1 if (v < 0 || v >= vertices.size) throw new Exception("参数v越界出错！"); for (int col = 0; col < vertices.size; col++) if (edge[v][col] > 0 && edge[v][col] < maxWeight) return col; return -1; } public int getNextNeighbor(int v1, int v2) throws Exception { // 取结点v1的邻接结点v2后的邻接结点 // 若存在返回该结点的下标序号，否则返回-1 if (v1 < 0 || v1 >= vertices.size || v2 < 0 || v2 >= vertices.size) throw new Exception("参数v1或v2越界出错！"); for (int col = v2 + 1; col < vertices.size; col++) if (edge[v1][col] > 0 && edge[v1][col] < maxWeight) return col; return -1; } /** * 深度优先遍历 * @param v * @param visited * @param vs * @throws Exception */ private void depthFirstSearch(int v, boolean[] visited, Visit vs) throws Exception { // 连通图以v为初始结点序号、访问操作为vs的深度优先遍历 // 数组visited标记了相应结点是否已访问过，0表示未访问，1表示已访问 vs.print(getValue(v)); // 访问该结点 visited[v] = true; // 置已访问标记 int w = getFirstNeighbor(v); // 取第一个邻接结点 while (w != -1) { // 当邻接结点存在时循环 if (!visited[w]) // 如果没有访问过 depthFirstSearch(w, visited, vs); // 以w为初始结点递归遍历 w = getNextNeighbor(v, w); // 取下一个邻接结点 } } /** * 广度优先遍历 * @param v * @param visited * @param vs * @throws Exception */ private void broadFirstSearch(int v, boolean[] visited, Visit vs) throws Exception { // 连通图以v为初始结点序号、访问操作为vs的广度优先遍历 // 数组visited标记了相应结点是否已访问过，0表示未访问，1表示已访问 int u, w; SeqQueue queue = new SeqQueue(); // 创建顺序队列queue vs.print(getValue(v)); // 访问结点v visited[v] = true; // 置已访问标记 queue.append(new Integer(v)); // 结点v入队列 while (!queue.isEmpty()) { // 队列非空时循环 u = ((Integer) queue.delete()).intValue(); // 出队列 w = getFirstNeighbor(u); // 取结点u的第一个邻接结点 while (w != -1) { // 当邻接结点存在时循环 if (!visited[w]) { // 若该结点没有访问过 vs.print(getValue(w)); // 访问结点w visited[w] = true; // 置已访问标记 queue.append(new Integer(w)); // 结点w入队列 } // 取结点u的邻接结点w的下一个邻接结点 w = getNextNeighbor(u, w); } } } /** * 非连通图的深度优先遍历 * @param vs * @throws Exception */ public void depthFirstSearch(Visit vs) throws Exception { boolean[] visited = new boolean[getNumOfVertices()]; for (int i = 0; i < getNumOfVertices(); i++) visited[i] = false; // 置所有结点均未访问过 for (int i = 0; i < getNumOfVertices(); i++) // 对每个结点循环 if (!visited[i]) // 如果该结点未访问 depthFirstSearch(i, visited, vs);// 以结点i为初始结点深度优先遍历 } /** * 非连通图的广度优先遍历 * @param vs * @throws Exception */ public void broadFirstSearch(Visit vs) throws Exception { boolean[] visited = new boolean[getNumOfVertices()]; for (int i = 0; i < getNumOfVertices(); i++) visited[i] = false; // 置所有结点均未访问过 for (int i = 0; i < getNumOfVertices(); i++) // 对每个结点循环 if (!visited[i]) // 如果该结点未访问过 broadFirstSearch(i, visited, vs);// 以结点i为初始结点广度优先遍历 }}
package cn.ls.path;import cn.ls.graph.AdjMWGraph;import cn.ls.graph.RowColWeight;/** * *测试类 */public class Exam8_4 { static final int maxVertices = 100; public static void createGraph(AdjMWGraph g, Object[] v, int n, RowColWeight[] rc, int e) throws Exception { for (int i = 0; i < n; i++) g.insertVertex(v[i]); for (int k = 0; k < e; k++) g.insertEdge(rc[k].row, rc[k].col, rc[k].weight); } public static void main(String[] args) { AdjMWGraph g = new AdjMWGraph(maxVertices); Character[] a = { new Character('A'), new Character('B'), new Character('C'), new Character('D'), new Character('E'), new Character('F') }; RowColWeight[] rcw = { new RowColWeight(0, 2, 5), new RowColWeight(0, 3, 30), new RowColWeight(1, 0, 2), new RowColWeight(1, 4, 8), new RowColWeight(2, 1, 15), new RowColWeight(2, 5, 7), new RowColWeight(4, 3, 4), new RowColWeight(5, 3, 10), new RowColWeight(5, 4, 18) }; int n = 6, e = 9;//6个结点9条边 try { createGraph(g, a, n, rcw, e); int[] distance = new int[n]; int[] path = new int[n]; Dijkstra.dijkstra(g, 0, distance, path); System.out.println("从顶点A到其他各顶点的最短距离为："); for (int i = 1; i < n; i++) System.out.println("到顶点" + g.getValue(i) + "的最短距离为：" + distance[i]); System.out.println("从顶点A到其他各顶点的前一顶点分别为："); for (int i = 0; i < n; i++) if (path[i] != -1) System.out.println("到顶点" + g.getValue(i) + "的前一顶点为：" + g.getValue(path[i])); } catch (Exception ex) { ex.printStackTrace(); } }}
测试结果：
从顶点A到其他各顶点的最短距离为：
到顶点B的最短距离为：20
到顶点C的最短距离为：5
到顶点D的最短距离为：22
到顶点E的最短距离为：28
到顶点F的最短距离为：12
从顶点A到其他各顶点的前一顶点分别为：
到顶点B的前一顶点为：C
到顶点C的前一顶点为：A
到顶点D的前一顶点为：F
到顶点E的前一顶点为：B
到顶点F的前一顶点为：C