代码:
- public class Djkstra {
- /*
- 单源最短路径
- 时间复杂度 O(ElogV) , 主要取决于优先队列的实现
- 空间复杂度 O(V)
- djkstr 和普通的 广度优先非常相似, 唯一多考虑了一点: 边有不同的权重 (不再一直是 1 了)
- 基于普通广度优先思想, 到达某个顶点的最短距离 = 到达这个顶点要经历的边的个数
- djkstr 的目的和普通广度优先算法一样, 希望对周围能到达的顶点, 再最早的时刻对其进行访问 (得到访问该顶点的最小成本)
- 那么问题是, 加上边的权重之后, 我们该如何将问题化为普通广度优先的思考方式呢?
- 一个办法是:
- 我们可以把一条加权的边想象成包含了匿名中间节点的数条边组成
- 例如
- 有一张图
- a-(4)->b
- \-(3)-^
- 一共有 2 条从 a 到 b 的边
- 权重为 3 的边 从 a 点到 b 点可以看成
- a-0-0-b (0 为匿名顶点)
- 同时
- a 到 b 点还有另外一条边, 权重是 4, 可以看成这样
- a-0-0-0-b
- 那么完整的图为
- a-0-0-0-b
- \-0-0--^
- 此时按照普通广度优先的思想, 从 a 点出发, 能先走到 b 点的一定是到达 b 点的最小成本, 是哪条边呢?
- 是权重小的那条边
- 所以我们在普通广度优先算法的基础上, 将一个普通的队列, 替换成一个优先队列
- 每当遇到周围可探索顶点的时候, 我们计算一下, 从当前顶点的成本 + 到达待探索顶点的边的成本 = 从当前点探索该点的成本
- 然后将待探索顶点和探索该点的成本放入优先队列 (若到达该点的路径有多个, 那么我们始终在优先队列中保留成本低的那个)
- 下次从优先队列中取出的顶点, 就是我们该探索的下一个顶点, 也就是能最先到达, 成本最低的那个顶点
- 题外:
- 类似的思想, 在加权无向图的最小生成树的 Prim 即时版中也有使用 (优先队列), 只不过它不累加探索成本到待探索点上, 而是直接
- 以探索某个点的最短路径的成本作为优先队列的排序条件 (这样能确保下一个探索的点, 是通过当前已知的成本最低的边走过去的 (一种贪心思想))
- 另外还有一个常用的最短路径算法: 贝尔曼福特,
- * */
- EdgeWeightedGraph ewg;
- IndexMinPQ<Float> minPQ;
- float[] cost; // 到达顶点 v 的成本
- Edge[] fromEdge; // 记录顶点 V 是从哪条边探索过来的, 除了顶点, 每个顶点有一条
- int s;
- public Djkstra(EdgeWeightedGraph ewg, int s) {
- this.ewg = ewg;
- this.s = s;
- minPQ = new IndexMinPQ<>(ewg.v());
- cost = new float[ewg.v()];
- fromEdge = new Edge[ewg.v()];
- for (int i = 0; i <cost.length; i++)
- cost[i] = Integer.MAX_VALUE;
- dj();
- this.ewg = null;
- }
- private void dj() {
- minPQ.insert(s + 1, 0f);
- while (!minPQ.isEmpty()) {
- int v = minPQ.topIndex() - 1; // 当前要探索的顶点
- float vcost = minPQ.delTop(); // 到达当前探索顶点的总成本
- cost[v] = vcost;
- for (Edge e : ewg.adj(v)) { // 将周围顶点入队
- int w = e.other(v); // 当前顶点的相邻顶点
- if (cost[w] != Integer.MAX_VALUE) // 已探索过的不再次探索
- continue;
- if (minPQ.contain(w + 1)) { // 若已经存在于优先队列中, 保留探索总成本小的
- if (minPQ.get(w + 1)> cost[v] + e.weight()) {
- minPQ.change(w + 1, cost[w] + e.weight());
- fromEdge[w] = e;
- }
- } else {
- minPQ.insert(w + 1, cost[v] + e.weight());
- fromEdge[w] = e; // 第一次探索到该顶点
- }
- }
- }
- }
- // 从起点到 v 点的总成本
- public float toVCost(int v) {
- return cost[v];
- }
- // 从起点, 是从哪条边到达 v 点的
- public Edge toVEdge(int v) {
- return fromEdge[v];
- }
- // 点到 v 点的路径
- public Stack<Edge> toVEdges(int v) {
- Stack<Edge> edges = new Stack<>();
- Edge e = fromEdge[v];
- int toV = v;
- while (e != null) {
- edges.push(e);
- toV = e.other(toV); // 到达当前点的来源点
- e = fromEdge[toV];
- }
- return edges;
- }
- public static void main(String[] args) {
- /*
- * (2)
- * 1 ---- 3
- * (2)/|\ |
- */ | \(3) |
- * 0 | \ |(2)
- * \ |(1)\ |
- * (1)\| \ |
- * 2 ---- 4
- * (4)
- * */
- EdgeWeightedGraph ewg = new EdgeWeightedGraph(5);
- ewg.addEdge(0, 1, 2);
- ewg.addEdge(0, 2, 1);
- ewg.addEdge(1, 2, 1);
- ewg.addEdge(1, 3, 2);
- ewg.addEdge(1, 4, 3);
- ewg.addEdge(2, 4, 4);
- ewg.addEdge(3, 4, 2);
- System.out.println(ewg);
- int s = 0;
- int w = 4;
- Djkstra dj = new Djkstra(ewg, s);
- System.out.println("from" + s + "to" + w + "'s path:");
- Stack<Edge> edges = dj.toVEdges(w);
- while (!edges.empty()) {
- Edge e = edges.pop();
- System.out.print(e + ",");
- }
- System.out.println();
- System.out.println("total cost :" + dj.toVCost(w));
- }
- }
输出
- 0: 0-1 2.00, 0-2 1.00,
- 1: 0-1 2.00, 1-2 1.00, 1-3 2.00, 1-4 3.00,
- 2: 0-2 1.00, 1-2 1.00, 2-4 4.00,
- 3: 1-3 2.00, 3-4 2.00,
- 4: 1-4 3.00, 2-4 4.00, 3-4 2.00,
- from 0 to 4's path:
- 0-2 1.00 , 2-4 4.00 ,
- total cost : 5.0
来源: http://www.bubuko.com/infodetail-3331782.html