算法8-7：最短路径接口

最短路径问题就是给定一个图，这个图中的边是有方向和权重的。求s到t的最短路径。

最短路径问题事实上分为非常多种。依照起点和终点来分，能够分为：

• 从一个顶点到还有一个顶点

• 从一个顶点到其它全部顶点

• 从全部顶点到全部顶点

依照边的权重来分能够分为：

• 非负权

• 随意权

• 欧几里德权

依照是否有环能够分为

• 无环最短路径

• 无负环最短路径

类的定义

在实现最短路径算法之前，须要先在程序中定义有向权重图。

有向权重边的定义例如以下：

public class DirectedEdge {
    private int v;
    private int w;
    private double weight;
 
    public DirectedEdge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
 
    public int from() {
        return v;
    }
 
    public int to() {
        return w;
    }
 
    public double weight() {
        return this.weight;
    }
 
    @Override
    public String toString() {
        return String.format("%s->%s[%s]", v, w, weight);
    }
}

有向权重图的定义例如以下：

import java.util.LinkedList;
 
public class EdgeWeightedDigraph {
    private int V;
    private LinkedList<DirectedEdge>[] adj;
 
    public EdgeWeightedDigraph(int V) {
        this.V = V;
        adj = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new LinkedList<DirectedEdge>();
        }
    }
 
    public void addEdge(DirectedEdge edge) {
        int v = edge.from();
        adj[v].add(edge);
    }
 
    public Iterable<DirectedEdge> adj(int v) {
        return adj[v];
    }
 
    public int V() {
        return V;
    }
 
    public int E() {
        int result = 0;
        for (LinkedList<DirectedEdge> e : adj) {
            result += e.size();
        }
        return result;
    }
 
    @Override
    public String toString() {
        String result = "";
        for (int i = 0; i < adj.length; i++) {
            result += i + ":";
            for (DirectedEdge e : adj[i]) {
                result += String.format(" %s[%s]", e.to(), e.weight());
            }
        }
        return result;
    }
}

这样定义有向权重图的优点就是能够有自连接，能够实现顶点之间有多个连接。

最短路径算法类的接口例如以下：

public class SP {
    public double distTo(int v);
    public Iterable<DirectedEdge> pathTo(int v);
}