首页 > 代码库 > 算法8-7:最短路径接口

算法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);
}