最短路径问题就是给定一个图，这个图中的边是有方向和权重的。求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
              
               [] adj;
       
          public EdgeWeightedDigraph(int V) {
              this.V = V;
              adj = new LinkedList[V];
              for (int i = 0; i < V; i++) {
                  adj[i] = new LinkedList
               
                (); } } public void addEdge(DirectedEdge edge) { int v = edge.from(); adj[v].add(edge); } public Iterable
                
                  adj(int v) { return adj[v]; } public int V() { return V; } public int E() { int result = 0; for (LinkedList
                 
                   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
              
                pathTo(int v);
      }