4.4　最短路径

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public class DirectedEdge{
    private final int v; // 边的起点
    private final int w; // 边的终点
    private final double weight; // 边的权重
    public DirectedEdge(int v, int w, double weight){
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    public double weight(){ return weight; }
    public int from(){ return v; }
    public int to(){ return w; }
    public String toString(){ return String.format("%d->%d %.2f", v, w, weight); }
}

public class EdgeWeightedDigraph{
    private final int V;//顶点总数
    private int E;//边的总数
    private Bag<DirectedEdge>[] adj;//邻接表
    public EdgeWeightedDigraph(int V){
        this.V = V;
        this.E = 0;
        adj=(Bag<DirectedEdge>[]) new Bag[V];
        for(int v=0;v<V;v++)
            adj[v]=new Bag<DirectedEdge>();
    }
    public EdgeWeightedDigraph(In in)

    public int V(){return V;}
    public int E(){return E;}
    public void addEdge(DirectedEdge e){
        adj[e.from()].add(e);
        E++;
    }
    public Iterable<DirectedEdge> adj(int v){return adj[v];}
    public Iterable<DirectedEdge> edges(){
        Bag<DirectedEdge> bag = new Bag<DirectedEdge>();
        for(int v=0;v<V;v++)
            for(DirectedEdge e:adj[v])
                bag.add(e);
        return bag;
    }
}