最短路徑問題就是給定一個圖，這個圖中的邊是有方向和權重的。求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);
      }