在Dijkstra算法的基础上作一些改动，可以扩展其功能。比如，可以在求得最短路径的基础上再列出一些次短的路径。做法是先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。（出处）
还是针对下图实验（视频出处），在计算出A->H的最短路径（60）后，应该可以找出2条次短路径（100和110）：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
final class Constants {
public final static int MAX_V = 1000000000;
}
final class Station {
public Station(final String name) {
this.name = name;
disSum = Constants.MAX_V;
previous = null;
}
public String getName() {
return this.name;
}
public int getDisSum() {
return this.disSum;
}
public void setDisSum(final int disSum) {
this.disSum = disSum;
}
public Station getPrevious() {
return this.previous;
}
public void setPrevious(final Station previous) {
this.previous = previous;
}
@Override
public boolean equals(Object s) {
return name.equals(((Station) s).name);
}
@Override
public String toString() {
return this.getClass().getSimpleName() + "[name=" + name + ", disSum=" + Integer.toString(disSum) + ", previous=" + (previous == null ? "null" : previous.name) + "]";
}
private final String name;
private int disSum;
private Station previous;
}
final class StationDisComparator implements Comparator<Station> {
@Override
public int compare(final Station s1, final Station s2) {
return s1.getDisSum() - s2.getDisSum();
}
}
final class Line {
public Line(final String start, final String end, final int dis) {
this.start = start;
this.end = end;
this.dis = dis;
}
public String getStart() {
return this.start;
}
public String getEnd() {
return this.end;
}
public int getDis() {
return this.dis;
}
public void setDis(final int dis) {
this.dis = dis;
}
@Override
public boolean equals(Object l) {
return start.equals(((Line) l).start) && end.equals(((Line) l).end);
}
@Override
public String toString() {
return this.getClass().getSimpleName() + "[start=" + start + ", end=" + end + ", dis=" + Integer.toString(dis) + "]";
}
private final String start;
private final String end;
private int dis;
}
public class Dijkstra {
/*
迪科斯彻算法(伪代码)
function Dijkstra(G, w, s)
for each vertex v in V[G] // 初始化
d[v] := infinity // 將各點的已知最短距離先設成無窮大
previous[v] := undefined // 各点的已知最短路径上的前趋都未知
d[s] := 0 // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
S := empty set
Q := set of all vertices
while Q is not an empty set // Dijkstra演算法主體
u := Extract_Min(Q)
S.append(u)
for each edge outgoing from u as (u,v)
if d[v] > d[u] + w(u,v) // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
d[v] := d[u] + w(u,v) // 更新路径长度到更小的那个和值。
previous[v] := u // 紀錄前趨頂點
*/
public static void dijkstra(final Map<String, Station> stations, final List<Line> lines, final String start, final String end) {
if (!stations.containsKey(start)) {
throw new IllegalArgumentException("start does not exist!");
}
for (Station s : stations.values()) {
s.setDisSum(Constants.MAX_V);
s.setPrevious(null);
}
stations.get(start).setDisSum(0);
Map<String, Station> s = new HashMap<String, Station>(stations.size());
Map<String, Station> q = new HashMap<String, Station>(stations.size());
q.putAll(stations);
while (!q.isEmpty()) {
Station u = Collections.min(q.values(), new StationDisComparator());
// System.out.println("u=" + u);
q.remove(u.getName());
s.put(u.getName(), u);
if (u.getName().equals(end)) {
break;
}
for (Line l : lines) {
if (l.getStart().equals(u.getName())) {
Station v = stations.get(l.getEnd());
// System.out.println("before v=" + v);
if (v.getDisSum() > u.getDisSum() + l.getDis()) {
v.setDisSum(u.getDisSum() + l.getDis());
v.setPrevious(u);
}
// System.out.println("after v=" + v);
}
}
}
}
public static void dijkstra(final Map<String, Station> stations, final List<Line> lines, final String start) {
dijkstra(stations, lines, start, null);
}
public static void showResult(final Map<String, Station> stations, final String end, boolean isPrintRoot) {
if (!stations.containsKey(end)) {
throw new IllegalArgumentException("end does not exist!");
}
Station s = stations.get(end);
System.out.println("Result:" + s);
if (isPrintRoot) {
List<Station> root = new ArrayList<Station>();
do {
root.add(0, s);
s = s.getPrevious();
} while (s != null);
System.out.println(root);
}
}
public static List<List<Line>> genRemovedLines(final Map<String, Station> stations, final List<Line> lines, final String end) {
if (!stations.containsKey(end)) {
throw new IllegalArgumentException("end does not exist!");
}
List<List<Line>> removedLinesCon = new ArrayList<List<Line>>();
Station e = stations.get(end);
do {
Station s = e.getPrevious();
if (s != null) {
List<Line> newLines = new ArrayList<Line>(lines.size());
newLines.addAll(lines);
newLines.remove(new Line(s.getName(), e.getName(), 0));
removedLinesCon.add(newLines);
}
e = s;
} while (e != null);
return removedLinesCon;
}
public static void main(String[] args) {
Map<String, Station> stations = new HashMap<String, Station>();
stations.put("A", new Station("A"));
stations.put("B", new Station("B"));
stations.put("C", new Station("C"));
stations.put("D", new Station("D"));
stations.put("E", new Station("E"));
stations.put("F", new Station("F"));
stations.put("G", new Station("G"));
stations.put("H", new Station("H"));
List<Line> lines = new ArrayList<Line>();
lines.add(new Line("A", "B", 20));
lines.add(new Line("A", "D", 80));
lines.add(new Line("A", "G", 90));
lines.add(new Line("B", "F", 10));
lines.add(new Line("C", "F", 50));
lines.add(new Line("C", "H", 20));
lines.add(new Line("C", "D", 10));
lines.add(new Line("D", "C", 10));
lines.add(new Line("D", "G", 20));
lines.add(new Line("E", "G", 30));
lines.add(new Line("E", "B", 50));
lines.add(new Line("F", "C", 10));
lines.add(new Line("F", "D", 40));
lines.add(new Line("G", "A", 20));
String start = "A";
String end = "H";
dijkstra(stations, lines, start, end);
boolean isPrintRoot = true;
showResult(stations, end, isPrintRoot);
List<List<Line>> removedLinesCon = genRemovedLines(stations, lines, end);
isPrintRoot = true;
for (List<Line> removedLines : removedLinesCon) {
// System.out.println(lines);
// System.out.println(removedLines);
dijkstra(stations, removedLines, start, end);
showResult(stations, end, isPrintRoot);
}
}
}
运行结果如下。这里只是打出了每次删除一条边后的计算结果，再加上排序还筛选处理就可以挑出两条次短路线了。
Result:Station[name=H, disSum=60, previous=C] [Station[name=A, disSum=0, previous=null], Station[name=B, disSum=20, previous=A], Station[name=F, disSum=30, previous=B], Station[name=C, disSum=40, previous=F], Station[name=H, disSum=60, previous=C]] Result:Station[name=H, disSum=1000000000, previous=null] [Station[name=H, disSum=1000000000, previous=null]] Result:Station[name=H, disSum=100, previous=C] [Station[name=A, disSum=0, previous=null], Station[name=B, disSum=20, previous=A], Station[name=F, disSum=30, previous=B], Station[name=D, disSum=70, previous=F], Station[name=C, disSum=80, previous=D], Station[name=H, disSum=100, previous=C]] Result:Station[name=H, disSum=110, previous=C] [Station[name=A, disSum=0, previous=null], Station[name=D, disSum=80, previous=A], Station[name=C, disSum=90, previous=D], Station[name=H, disSum=110, previous=C]] Result:Station[name=H, disSum=110, previous=C] [Station[name=A, disSum=0, previous=null], Station[name=D, disSum=80, previous=A], Station[name=C, disSum=90, previous=D], Station[name=H, disSum=110, previous=C]]
/********************************************************************
* 不落魄的书生的记事簿[blog.csdn.net/songyuanyao]
********************************************************************/