迪科斯彻算法使用广度优先搜索在非负权有向图上解决单源最短路径问题。
算法说明依据在这里。
没有经过仔细测试，用下图的这个例子试了一下没问题。（视频出处）
代码贴在下面，通过指定参数的变化可以算出到指定终点的最短路径（循环会中途结束），或者从起点到所有节点的最短路径（循环到所有节点都计算完毕为止）。
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 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;
}
private final String start;
private final String end;
private final 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 // 紀錄前趨頂點
*/
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>();
Map<String, Station> q = new HashMap<String, Station>();
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);
}
}
}
}
static void dijkstra(final Map<String, Station> stations, final List<Line> lines, final String start) {
dijkstra(stations, lines, start, null);
}
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 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));
dijkstra(stations, lines, "A");
boolean isPrintRoot = true;
showResult(stations, "A", isPrintRoot);
showResult(stations, "B", isPrintRoot);
showResult(stations, "C", isPrintRoot);
showResult(stations, "D", isPrintRoot);
showResult(stations, "E", isPrintRoot);
showResult(stations, "F", isPrintRoot);
showResult(stations, "G", isPrintRoot);
showResult(stations, "H", isPrintRoot);
}
}
运行结果如下，1000000000是最大值，表示无路可通。Result:Station[name=A, disSum=0, previous=null] [Station[name=A, disSum=0, previous=null]] Result:Station[name=B, disSum=20, previous=A] [Station[name=A, disSum=0, previous=null], Station[name=B, disSum=20, previous=A]] Result:Station[name=C, disSum=40, previous=F] [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]] Result:Station[name=D, disSum=50, 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=D, disSum=50, previous=C]] Result:Station[name=E, disSum=1000000000, previous=null] [Station[name=E, disSum=1000000000, previous=null]] Result:Station[name=F, disSum=30, previous=B] [Station[name=A, disSum=0, previous=null], Station[name=B, disSum=20, previous=A], Station[name=F, disSum=30, previous=B]] Result:Station[name=G, disSum=70, previous=D] [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=D, disSum=50, previous=C], Station[name=G, disSum=70, previous=D]] 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]]
/********************************************************************
* 不落魄的书生的记事簿[blog.csdn.net/songyuanyao]
********************************************************************/