溫習Algs4 (六):有向帶權圖,最短路徑

有向帶權圖, 最短路徑

• 有向帶權圖
• • WeightedDirectedEdge.java
  • EdgeWeightedDigraph.java
• 最短路徑
• • SP.java
  • Dijkstra算法
  • • Dijkstra.java
  • Bellman-Ford最短路徑算法
  • • BellmanFord.java
  • 算法比較

有向帶權圖

有向帶權圖的API和有向圖的幾乎一樣, 不再贅述

WeightedDirectedEdge.java

/******************************************************************************
 *  Compilation:  javac WeightedDirectedEdge.java
 *  Execution:    java WeightedDirectedEdge
 *  Author:       Chenghao Wang
 ******************************************************************************/

public class WeightedDirectedEdge implements Comparable<WeightedDirectedEdge> {
    private int from;
    private int to;
    private double weight;

    WeightedDirectedEdge() { }
    WeightedDirectedEdge(int from, int to, double weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    public int from() {
        return from;
    }

    public int to() {
        return to;
    }

    public double weight() {
        return weight;
    }

    @Override
    public int compareTo(WeightedDirectedEdge other) {
        if (weight < other.weight) return -1;
        if (weight > other.weight) return +1;
        return 0;
    }

    @Override
    public String toString() {
        return String.format("%d -> %d (%.2f)\n", from, to, weight);
    }
}
           

EdgeWeightedDigraph.java

/******************************************************************************
 *  Compilation:  javac EdgeWeightedDigraph.java
 *  Execution:    java EdgeWeightedDigraph
 *  Author:       Chenghao Wang
 ******************************************************************************/
import java.util.Scanner;

public class EdgeWeightedDigraph {
    private int vertexCount;
    private int edgeCount;
    private Bag<WeightedDirectedEdge>[] adj;
    private Bag<WeightedDirectedEdge> edges;

    EdgeWeightedDigraph() { }
    EdgeWeightedDigraph(int vertexCount) {
        this.vertexCount = vertexCount;
        edgeCount = 0;
        edges = new Bag<WeightedDirectedEdge>();
        adj = (Bag<WeightedDirectedEdge>[]) new Bag[vertexCount];
        for (int i = 0; i < vertexCount; i++) {
            adj[i] = new Bag<WeightedDirectedEdge>();
        }
    }

    EdgeWeightedDigraph(Scanner scan) {
        this(scan.nextInt());
        int e = scan.nextInt();
        for (int i = 0; i < e; i++) {
            int from = scan.nextInt();
            int to = scan.nextInt();
            double w = scan.nextDouble();
            addEdge(from, to, w);
        }
    }

    public int V() {
        return vertexCount;
    }

    public int E() {
        return edgeCount;
    }

    public void addEdge(int from, int to, double w) {
        WeightedDirectedEdge edge = new WeightedDirectedEdge(from, to, w);
        adj[from].add(edge);
        edgeCount++;
        edges.add(edge);
    }

    public void addEdge(WeightedDirectedEdge edge) {
        adj[edge.from()].add(edge);
        edges.add(edge);
        edgeCount++;
    }

    public Iterable<WeightedDirectedEdge> adj(int v) {
        return adj[v];
    }

    public Iterable<WeightedDirectedEdge> edges() {
        return edges;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("<EdgeWeightedDigraph>\n");
        for (int i = 0; i < vertexCount; i++) {
            for (WeightedDirectedEdge e : adj[i]) {
                sb.append("    " + e.toString());
            }
        }
        sb.append("</EdgeWeightedDigraph>\n");
        return sb.toString();
    }
}
           

最短路徑

先介紹一個公共抽象類 SP (Shortest Path), 即最短路徑的API. 它有兩個對外接口:

1. distanceTo(int v) 傳回從起點到v的距離
2. pathTo(int v) 傳回最短路中到達v的上一個節點

SP.java

/******************************************************************************
 *  Compilation:  javac SP.java
 *  Execution:    java SP
 *  Author:       Chenghao Wang
 ******************************************************************************/

public abstract class SP {
    protected double[] dist;
    protected EdgeWeightedDigraph g;
    protected int[] path;

    SP() { }
    SP(EdgeWeightedDigraph g, int s) {
        this.g = g;
        dist = new double[g.V()];
        path = new int[g.V()];
        for (int i = 0; i < g.V(); i++) {
            dist[i] = Double.POSITIVE_INFINITY;
        }
        dist[s] = 0;
        path[s] = s;
    }

    public double distanceTo(int v) {
        return dist[v];
    }

    public int pathTo(int v) {
        return path[v];
    }
}
           

Dijkstra算法

接下來介紹著名Dijstra算法, 它的邏輯是: 初始化起點到所有其他點的距離為無限大, 然後每次選取距離起點最近的點, 接着周遊該點的所有鄰接點 v, 更新起點到 v 的距離.

Dijkstra.java

/******************************************************************************
 *  Compilation:  javac Dijkstra.java
 *  Execution:    java Dijkstra
 *  Author:       Chenghao Wang
 ******************************************************************************/

public class Dijkstra extends SP {
    private IndexPQ<Double> pq;

    Dijstra() { }
    Dijstra(EdgeWeightedDigraph g, int s) {
        super(g, s);
        pq = new IndexPQ(IndexPQ.MIN_PQ, g.V());
        pq.push(s, 0.0);
        while (!pq.isEmpty()) {
            int v = pq.pop();
            for (WeightedDirectedEdge e : g.adj(v)) {
                int next = e.to();
                double newDist = dist[v] + e.weight();
                if (dist[next] > newDist) {
                    dist[next] = newDist;
                    pq.push(next, newDist);
                    path[next] = v;
                }
            }
        }
    }
}
           

Bellman-Ford最短路徑算法

Bellman-Ford算法能夠用于負權圖, (Dijstra算法則不能), 且邏輯較為簡單, 但其時間複雜度更高.

BellmanFord.java

/******************************************************************************
 *  Compilation:  javac BellmanFord.java
 *  Execution:    java BellmanFord
 *  Author:       Chenghao Wang
 ******************************************************************************/

public class BellmanFord extends SP {

    BellmanFord() { }
    BellmanFord(EdgeWeightedDigraph g, int s) {
        super(g, s);
        
        for (int i = 0; i < g.V(); i++) {
            for (WeightedDirectedEdge e : g.edges()) {
                if (dist[e.from()] == Double.POSITIVE_INFINITY) {
                    continue;
                }
                else if (dist[e.to()] > (dist[e.from()] + e.weight())) {
                    dist[e.to()] = dist[e.from()] + e.weight();
                    path[e.to()] = e.from();
                }
            }
        }
    }
}
           

算法比較

算法	時間複雜度	适用場合
Dijkstra	Elog(V)	僅正權圖
Bellman-Ford	EV	所有圖都可以