一吉拳、問(wèn)題介紹
1.求K條最短路徑的必要性
最短路徑問(wèn)題分為：
- 單源最短路徑
- 所有頂點(diǎn)對(duì)間的最短路徑
共同的缺陷：
這里的最短路徑指兩點(diǎn)間最短的那一條路徑牧牢，不包括次短艾帐、再次短等路徑丑蛤。這樣的最短路徑問(wèn)題比較狹義录平。
在實(shí)際情況中麻车，例如：用戶在使用咨詢系統(tǒng)或決策支持系統(tǒng)時(shí)，希望得到最優(yōu)的決策參考外斗这，還希望得到次優(yōu)动猬、再次優(yōu)等決策參考，這同樣反映在最短路徑問(wèn)題上表箭。因此有必要將最短路徑問(wèn)題予以擴(kuò)展和延伸赁咙，稱為K條最短路徑問(wèn)題，即不但要求得最短路徑，還要求得次短彼水、再次短等路徑崔拥。
2.KSP問(wèn)題定義
KSP問(wèn)題是對(duì)最短路徑問(wèn)題的推廣，它除了要確定最短路徑之外凤覆，還要確定次短路徑链瓦、第三短路徑，...盯桦，知道找到第K短路徑慈俯。用Pi表示從起點(diǎn)s到終點(diǎn)t的第i短路徑，KSP問(wèn)題是確定路徑集合Pk={p1,p2,p3,...,pk}俺附，使得滿足以下3個(gè)條件：
1）K條路徑是按次序產(chǎn)生的肥卡，即對(duì)于所有的i（i=1,2,...,K-1）溪掀，pi是在pi+1之前確定事镣；
2）K條路徑是按長(zhǎng)度從小到大排列的，即對(duì)于所有的i（i=1,2,...,K-1）揪胃，都有c(pi)<c(pi+1)璃哟；
3）這K條路徑是最短的，即對(duì)于所有的p∈Pst-PK喊递，都有c(pk)<c(p)随闪。
3.相關(guān)概念
設(shè)起點(diǎn)為 1 ，終點(diǎn)為 5 骚勘。p1铐伴、p2、p3 分別表示起點(diǎn)到終點(diǎn)間最短路徑俏讹、第二短路徑当宴、第三短路徑。
1）偏離點(diǎn)
p3相對(duì)于p1的偏離節(jié)點(diǎn)為節(jié)點(diǎn) 2
2）偏離邊
p3相對(duì)于p1的偏離邊為(2,4)
3）偏離路徑
p3相對(duì)于p1的(2,4,5)
4.KSP算法分類
1） 一般KSP問(wèn)題
對(duì)路徑?jīng)]有任何限制
2） 限定無(wú)環(huán)KSP問(wèn)題
要求所有路徑都是簡(jiǎn)單路徑泽疆，不能有環(huán)
當(dāng)路徑中所有節(jié)點(diǎn)都不同時(shí)户矢，稱為無(wú)環(huán)路徑
兩類KSP問(wèn)題具有不同的特征，分別提出了不同的求解算法殉疼，分別稱之為
- 一般的KSP算法
- 限定無(wú)環(huán)KSP算法
二梯浪、思路
下面列出用Yen's算法求KSP的代碼。該算法是Yen在1971年提出的以其名字命名的Yen算法瓢娜。算法采用了遞推法中的偏離路徑算法思想挂洛，適用于非負(fù)權(quán)邊的有向無(wú)環(huán)圖。
1.流程圖
Q：將什么樣的點(diǎn)做為偏離點(diǎn)
在
pk的基礎(chǔ)上求pk+1時(shí)眠砾，將pk的路徑上除終點(diǎn)d之外的節(jié)點(diǎn)分別作為偏離點(diǎn)
Q：求Vi到終點(diǎn)d的最短路徑
設(shè)起點(diǎn)為s虏劲，終點(diǎn)為t，偏離點(diǎn)為Vi。求偏離點(diǎn)到終點(diǎn)的最短路徑時(shí)要注意兩個(gè)問(wèn)題
- 防止從起點(diǎn)到終點(diǎn)的整體路徑有環(huán)
從Vi到t的最短路徑不能包含s到Vi的路徑上的任何節(jié)點(diǎn) - 避免與已經(jīng)在結(jié)果列表中的路徑重復(fù)
從Vi發(fā)出的邊不能與結(jié)果列表中的路徑p1,p2,...pk伙单，上從Vi發(fā)出邊的相同
這個(gè)體現(xiàn)在代碼上就是：在用Dijkstra算法算最短路徑時(shí)對(duì)數(shù)組的初始化要進(jìn)行特別處理
// 不能走的邊
if (unavailableEdges != null && unavailableEdges.size() != 0) {
for (MyPath p: unavailableEdges) {
int index = p.path.indexOf(startIndex);
if (index >= 0 && (index + 1) >= 0) {
dist[index + 1] = Double.MAX_VALUE;
path[index + 1] = -1;
}
}
}
// 不能走的點(diǎn)
if (unavailableNodeIndexs != null && unavailableNodeIndexs.size() != 0) {
for (Integer point: unavailableNodeIndexs) {
set[point] = 1;
}
}
Q：每次找到新的最短路徑時(shí)获高，需將該路徑從候選鏈列表中移除，并加入到結(jié)果列表中
Q：候選列表中的路徑不能重復(fù)
所以選擇用
Set來(lái)存儲(chǔ)候選路徑吻育，去重
Q：如何從候選列表中選出合適的路徑
如果只有一條路徑權(quán)值和最小的路：將該路徑返回念秧；
如果路徑權(quán)值和最小的路有多條：從其中選出節(jié)點(diǎn)數(shù)最少的路徑。
2.手工模擬求K最短路徑流程
求C到H的10條最短路徑
節(jié)點(diǎn)加載內(nèi)存后存儲(chǔ)在Node[] nodes數(shù)組中布疼，各個(gè)節(jié)點(diǎn)在數(shù)組中的存儲(chǔ)位置如下摊趾，下面用各個(gè)點(diǎn)的數(shù)組下標(biāo)進(jìn)行說(shuō)明。表格中括號(hào)中備注為路徑權(quán)重游两。
1）通過(guò)最短路徑算法Dijkstra得到C到H的最短路徑
p1=C-E-F-H砾层，即0-2-3-5
2）在p1的基礎(chǔ)上求p2
遍歷完各個(gè)偏離點(diǎn)后的情況：
從集合B中選出路徑0->2->4->5(7)移除，并加入到集合A中贱案，作為p2
3）在p2的基礎(chǔ)上求p3
遍歷完各個(gè)偏離點(diǎn)后的情況：
從集合B中選出路徑0->1->3->5(8)移除肛炮，并加入到集合A中，作為p3
4）在p3的基礎(chǔ)上求p4
遍歷完各個(gè)偏離點(diǎn)后的情況：
從集合B中選出路徑0->1->3->5(8)移除宝踪，并加入到集合A中侨糟，作為p4
5）在p4的基礎(chǔ)上求p5
遍歷完各個(gè)偏離點(diǎn)后的情況：
從集合B中選出路徑0->2->3->4->5(8)移除，并加入到集合A中瘩燥，作為p5`
6）在p5的基礎(chǔ)上求p6
遍歷完各個(gè)偏離點(diǎn)后秕重，沒(méi)有新的候選路徑加入集合B中
從集合B中選出路徑0->1->3->4->5(11)移除，并加入到集合A中厉膀，作為p6
7）在p6的基礎(chǔ)上求p7
遍歷各個(gè)偏離點(diǎn)時(shí)求最短路徑均不存在溶耘，故遍歷完各個(gè)偏離點(diǎn)后，沒(méi)有新的候選路徑加入集合B中服鹅，從集合B中選出路徑0->2->1->3->4->5(11)移除凳兵，并加入到集合A中，作為p7
8）在p7的基礎(chǔ)上求p8
遍歷各個(gè)偏離點(diǎn)時(shí)求最短路徑均不存在菱魔，故遍歷完各個(gè)偏離點(diǎn)后留荔，沒(méi)有新的候選路徑加入集合B中，候選集合為空澜倦，不能再繼續(xù)向下尋找聚蝶。故從C到H共有7條路徑。
三藻治、代碼
1.輸入上述圖
6 9
11 C
12 D
13 E
14 F
15 G
16 H
11 12 3
11 13 2
12 14 4
13 12 1
13 14 2
13 15 3
14 15 2
14 16 1
15 16 2
11 16 10
2.代碼
package road;
import util.NavigationUtil;
import java.util.*;
/**
* <pre>
* author : 楊麗金
* time : 2018/11/14
* desc : 有關(guān)于圖的最短路徑
* version: 1.0
* </pre>
*/
public class ShortestPath {
public static class MyPath {
// 路徑上的各個(gè)節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組下標(biāo)（從起點(diǎn)到終點(diǎn)）
public List < Integer > path;
// 路徑總權(quán)值
public double weight;
// 路徑上節(jié)點(diǎn)個(gè)數(shù)：通過(guò)path.size()得到
public MyPath() {}
public MyPath(List < Integer > path, double weight) {
this.path = path;
this.weight = weight;
}
@Override
public String toString() {
return "MyPath{" +
"path=" + path +
", weight=" + weight +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MyPath path1 = (MyPath) o;
return path != null ? path.equals(path1.path) : path1.path == null;
}
@Override
public int hashCode() {
int result;
long temp;
result = path != null ? path.hashCode() : 0;
temp = Double.doubleToLongBits(weight);
result = 31 * result + (int)(temp ^ (temp >>> 32));
return result;
}
}
/**
* 用Yen's KSP算法從圖中找出從startIndex到endIndex的K條最短路徑
*
* @param g
* @param startIndex:起始節(jié)點(diǎn)的數(shù)組下標(biāo)
* @param endIndex：終止節(jié)點(diǎn)的數(shù)組下標(biāo)
* @param K：要求的最短路徑數(shù)目
* @return
*/
public List < MyPath > KSP_Yen(MyGraph g, int startIndex, int endIndex, int K) {
// 結(jié)果列表
List < MyPath > result = new ArrayList < > ();
// 候選路徑列表
Set < MyPath > candidatePaths = new HashSet < > ();
// 候選路徑列表中權(quán)值最小的路徑碘勉，及其對(duì)應(yīng)的節(jié)點(diǎn)個(gè)數(shù)
// 第一條最短路徑
MyPath p1 = getSingleShortestPath_dijkstra(g, startIndex, endIndex, null, null);
result.add(p1);
int k = 1;
List < Integer > pk = p1.path;
while (k < K) {
/*
求第k+1條最短路徑
*/
// 遍歷每一個(gè)偏離點(diǎn)
for (int i = 0; i <= pk.size() - 2; i++) {
// 1，pk路徑中起點(diǎn)到偏離點(diǎn)Vi的路徑權(quán)值
double w1 = 0;
for (int j = 0; j <= i - 1; j++) {
w1 += NavigationUtil.getEdgeWight(g, pk.get(j), pk.get(j + 1));
}
// 2,偏離點(diǎn)到終點(diǎn)的最短路徑
MyPath viToDestinationSP = getSingleShortestPath_dijkstra(g,
pk.get(i), endIndex, pk.subList(0, i), result);
if (viToDestinationSP != null) {
// 說(shuō)明從這個(gè)偏離點(diǎn)可以到達(dá)終點(diǎn)
MyPath temp = new MyPath();
List < Integer > tempPath = new ArrayList < > (pk.subList(0, i));
tempPath.addAll(viToDestinationSP.path);
temp.path = tempPath;
temp.weight = w1 + viToDestinationSP.weight;
// 加入候選列表
if (!candidatePaths.contains(temp)) {
candidatePaths.add(temp);
}
}
}
if (candidatePaths == null || candidatePaths.size() == 0) {
// 沒(méi)有候選路徑桩卵，則無(wú)需再繼續(xù)向下求解
break;
} else {
// 從候選路徑中選出最合適的一條验靡，移除并加入到結(jié)果列表
MyPath fitPath = getFitPathFromCandidate(candidatePaths);
candidatePaths.remove(fitPath);
result.add(fitPath);
k++;
pk = fitPath.path;
}
}
return result;
}
/**
* 從候選列表中得到一條路徑作為pk+1
* 要求：1）該路徑的權(quán)值和最斜侗觥；2）路徑經(jīng)過(guò)節(jié)點(diǎn)數(shù)最少
* @param candidatePaths：候選列表
* @return
*/
private MyPath getFitPathFromCandidate(Set < MyPath > candidatePaths) {
MyPath result = new MyPath(null, Double.MAX_VALUE);
for (MyPath p: candidatePaths) {
// 對(duì)于每一條路徑
if (p.weight < result.weight) {
result = p;
}
if (p.weight == result.weight && p.path.size() < result.path.size()) {
result = p;
}
}
return result;
}
/**
* 用Dijkstra算法得到從startIndex到endIndex的一條最短路徑
*
* @param g
* @param startIndex 起始節(jié)點(diǎn)的數(shù)組下標(biāo)
* @param endIndex 終止節(jié)點(diǎn)的數(shù)組下標(biāo)
* @param unavailableNodeIndexs：求最短路徑時(shí)不可用的節(jié)點(diǎn)（數(shù)組下標(biāo)）
* @param unavailableEdges：求最短路徑時(shí)不可用的邊
* @return
*/
public MyPath getSingleShortestPath_dijkstra(MyGraph g, int startIndex, int endIndex,
List < Integer > unavailableNodeIndexs, List < MyPath > unavailableEdges) {
if (startIndex == -1) {
// throw new Exception("getSingleShortestPath_dijkstra()起始點(diǎn)編號(hào)輸入錯(cuò)誤");
}
if (endIndex == -1) {
// throw new Exception("getSingleShortestPath_dijkstra()終止點(diǎn)編號(hào)輸入錯(cuò)誤");
}
int[] set = new int[g.n]; // 是否已并入集合胜嗓，該點(diǎn)是否已找到最短路徑
// s到i的最短路徑長(zhǎng)度
double[] dist = new double[g.n];
// s到i的最短路徑上i的前一個(gè)節(jié)點(diǎn)編號(hào)
int[] path = new int[g.n];
// 初始化數(shù)組
set[startIndex] = 1;
for (int i = 0; i < g.n; i++) {
if (i == startIndex) { // 源點(diǎn)
dist[i] = 0;
path[i] = -1;
} else {
if (NavigationUtil.isConnected(g, startIndex, i)) {
dist[i] = NavigationUtil.getEdgeWight(g, startIndex, i);
path[i] = startIndex;
} else {
dist[i] = Double.MAX_VALUE;
path[i] = -1;
}
}
}
// 不能走的邊
if (unavailableEdges != null && unavailableEdges.size() != 0) {
for (MyPath p: unavailableEdges) {
int index = p.path.indexOf(startIndex);
if (index >= 0 && (index + 1) >= 0) {
dist[p.path.get(index + 1)] = Double.MAX_VALUE;
path[p.path.get(index + 1)] = -1;
}
}
}
// 不能走的點(diǎn)
if (unavailableNodeIndexs != null && unavailableNodeIndexs.size() != 0) {
for (Integer point: unavailableNodeIndexs) {
set[point] = 1;
}
}
// 需進(jìn)行n-2輪循環(huán)
for (int i = 0; i < g.n - 2; i++) {
int k = -1;
double min = Double.MAX_VALUE;
// 找出dist[]中最小的（太貪心了）
for (int j = 0; j < g.n; j++) {
if (set[j] == 1) {
continue;
}
if (dist[j] < min) {
min = dist[j];
k = j;
}
}
if (k == -1) {
// 說(shuō)明從源點(diǎn)出發(fā)與其余節(jié)點(diǎn)不連通高职，無(wú)法再向下進(jìn)行擴(kuò)展
break;
}
set[k] = 1; // 把節(jié)點(diǎn)k并入
// 修改dist[]、path[]
for (int j = 0; j < g.n; j++) {
if (set[j] == 1) {
continue;
}
if (NavigationUtil.isConnected(g, k, j)) {
double temp = dist[k] + NavigationUtil.getEdgeWight(g, k, j);
if (temp < dist[j]) {
dist[j] = temp;
path[j] = k;
}
}
}
}
System.out.println("運(yùn)行Dijkstra算法后的數(shù)組情況為：");
System.out.print("set[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(set[i] + "\t");
}
System.out.println();
System.out.print("dist[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(dist[i] + "\t");
}
System.out.println();
System.out.print("path[]:");
for (int i = 0; i < g.n; i++) {
System.out.print(path[i] + "\t");
}
System.out.println();
// 輸出
if (dist[endIndex] == Double.MAX_VALUE) {
// 說(shuō)明沒(méi)有最短路徑辞州，兩點(diǎn)不連通
System.out.println("兩點(diǎn)之間不連通");
return null;
} else {
System.out.println("節(jié)點(diǎn)" + g.nodes[startIndex].nodeId + "到節(jié)點(diǎn)" +
g.nodes[endIndex].nodeId + "的最短路徑長(zhǎng)度為：" + dist[endIndex] + "怔锌，具體路徑是：");
MyPath result = new MyPath();
result.path = getMinimumPath(g, startIndex, endIndex, path);
result.weight = dist[endIndex];
return result;
}
}
/**
* 輸出從節(jié)點(diǎn)S到節(jié)點(diǎn)T的最短路徑
*
* @param sIndex：起始節(jié)點(diǎn)在數(shù)組中下標(biāo)
* @param tIndex：終止節(jié)點(diǎn)在數(shù)組中下標(biāo)
*/
private List < Integer > getMinimumPath(MyGraph g, int sIndex, int tIndex, int[] path) {
List < Integer > result = new ArrayList < > ();
Stack < Integer > stack = new Stack < > ();
stack.push(tIndex);
int i = path[tIndex];
while (i != -1) {
stack.push(i);
i = path[i];
}
while (!stack.isEmpty()) {
System.out.print(g.nodes[stack.peek()].nodeId + ":" + g.nodes[stack.peek()].nodeName + "-->");
result.add(NavigationUtil.getIndex(g, g.nodes[stack.pop()].nodeId));
}
System.out.println();
return result;
}
}
3.輸出
sps: [MyPath {
path = [0, 2, 3, 5], weight = 5.0
}, MyPath {
path = [0, 2, 4, 5], weight = 7.0
}, MyPath {
path = [0, 1, 3, 5], weight = 8.0
}, MyPath {
path = [0, 2, 1, 3, 5], weight = 8.0
}, MyPath {
path = [0, 2, 3, 4, 5], weight = 8.0
}, MyPath {
path = [0, 1, 3, 4, 5], weight = 11.0
}, MyPath {
path = [0, 2, 1, 3, 4, 5], weight = 11.0
}]
參考文獻(xiàn)
[1]K條最短路徑問(wèn)題綜述
[2]韓海玲. 基于城市路網(wǎng)的最短路徑算法研究與應(yīng)用[D]. 中北大學(xué), 2017.
[3]徐濤, 丁曉璐, 李建伏. K最短路徑算法綜述[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2013, 34(11):3900-3906.
[4]K條最短路徑算法(KSP, k-shortest pathes)：Yen's Algorithm
