温习Algs4 (六):有向带权图,最短路径

男娘i 2022-04-08 10:10 186阅读 0赞

### 有向带权图, 最短路径 ###

*  有向带权图
 *   *  WeightedDirectedEdge.java
     *  EdgeWeightedDigraph.java
 *  最短路径
 *   *  SP.java
     *  Dijkstra算法
     *   *  Dijkstra.java
     *  Bellman-Ford最短路径算法
     *   *  BellmanFord.java
     *  算法比较

# 有向带权图 #

有向带权图的API和有向图的几乎一样, 不再赘述

## WeightedDirectedEdge.java ##

/****************************************************************************** * Compilation: javac WeightedDirectedEdge.java * Execution: java WeightedDirectedEdge * Author: Chenghao Wang ******************************************************************************/
    
    public class WeightedDirectedEdge implements Comparable<WeightedDirectedEdge> { 
        private int from;
        private int to;
        private double weight;
    
        WeightedDirectedEdge() {  }
        WeightedDirectedEdge(int from, int to, double weight) { 
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    
        public int from() { 
            return from;
        }
    
        public int to() { 
            return to;
        }
    
        public double weight() { 
            return weight;
        }
    
        @Override
        public int compareTo(WeightedDirectedEdge other) { 
            if (weight < other.weight) return -1;
            if (weight > other.weight) return +1;
            return 0;
        }
    
        @Override
        public String toString() { 
            return String.format("%d -> %d (%.2f)\n", from, to, weight);
        }
    }

## EdgeWeightedDigraph.java ##

/****************************************************************************** * Compilation: javac EdgeWeightedDigraph.java * Execution: java EdgeWeightedDigraph * Author: Chenghao Wang ******************************************************************************/
    import java.util.Scanner;
    
    public class EdgeWeightedDigraph { 
        private int vertexCount;
        private int edgeCount;
        private Bag<WeightedDirectedEdge>[] adj;
        private Bag<WeightedDirectedEdge> edges;
    
        EdgeWeightedDigraph() {  }
        EdgeWeightedDigraph(int vertexCount) { 
            this.vertexCount = vertexCount;
            edgeCount = 0;
            edges = new Bag<WeightedDirectedEdge>();
            adj = (Bag<WeightedDirectedEdge>[]) new Bag[vertexCount];
            for (int i = 0; i < vertexCount; i++) { 
                adj[i] = new Bag<WeightedDirectedEdge>();
            }
        }
    
        EdgeWeightedDigraph(Scanner scan) { 
            this(scan.nextInt());
            int e = scan.nextInt();
            for (int i = 0; i < e; i++) { 
                int from = scan.nextInt();
                int to = scan.nextInt();
                double w = scan.nextDouble();
                addEdge(from, to, w);
            }
        }
    
        public int V() { 
            return vertexCount;
        }
    
        public int E() { 
            return edgeCount;
        }
    
        public void addEdge(int from, int to, double w) { 
            WeightedDirectedEdge edge = new WeightedDirectedEdge(from, to, w);
            adj[from].add(edge);
            edgeCount++;
            edges.add(edge);
        }
    
        public void addEdge(WeightedDirectedEdge edge) { 
            adj[edge.from()].add(edge);
            edges.add(edge);
            edgeCount++;
        }
    
        public Iterable<WeightedDirectedEdge> adj(int v) { 
            return adj[v];
        }
    
        public Iterable<WeightedDirectedEdge> edges() { 
            return edges;
        }
    
        @Override
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            sb.append("<EdgeWeightedDigraph>\n");
            for (int i = 0; i < vertexCount; i++) { 
                for (WeightedDirectedEdge e : adj[i]) { 
                    sb.append(" " + e.toString());
                }
            }
            sb.append("</EdgeWeightedDigraph>\n");
            return sb.toString();
        }
    }

# 最短路径 #

先介绍一个公共抽象类 SP (Shortest Path), 即最短路径的API. 它有两个对外接口:

1.  distanceTo(int v) 返回从起点到v的距离
2.  pathTo(int v) 返回最短路中到达v的上一个节点

## SP.java ##

/****************************************************************************** * Compilation: javac SP.java * Execution: java SP * Author: Chenghao Wang ******************************************************************************/
    
    public abstract class SP { 
        protected double[] dist;
        protected EdgeWeightedDigraph g;
        protected int[] path;
    
        SP() {  }
        SP(EdgeWeightedDigraph g, int s) { 
            this.g = g;
            dist = new double[g.V()];
            path = new int[g.V()];
            for (int i = 0; i < g.V(); i++) { 
                dist[i] = Double.POSITIVE_INFINITY;
            }
            dist[s] = 0;
            path[s] = s;
        }
    
        public double distanceTo(int v) { 
            return dist[v];
        }
    
        public int pathTo(int v) { 
            return path[v];
        }
    }

## Dijkstra算法 ##

接下来介绍著名Dijstra算法, 它的逻辑是: 初始化起点到所有其他点的距离为无限大, 然后每次**选取距离起点最近**的点, 接着遍历该点的所有邻接点 *v*, 更新起点到 *v* 的距离.

### Dijkstra.java ###

/****************************************************************************** * Compilation: javac Dijkstra.java * Execution: java Dijkstra * Author: Chenghao Wang ******************************************************************************/
    
    public class Dijkstra extends SP { 
        private IndexPQ<Double> pq;
    
        Dijstra() {  }
        Dijstra(EdgeWeightedDigraph g, int s) { 
            super(g, s);
            pq = new IndexPQ(IndexPQ.MIN_PQ, g.V());
            pq.push(s, 0.0);
            while (!pq.isEmpty()) { 
                int v = pq.pop();
                for (WeightedDirectedEdge e : g.adj(v)) { 
                    int next = e.to();
                    double newDist = dist[v] + e.weight();
                    if (dist[next] > newDist) { 
                        dist[next] = newDist;
                        pq.push(next, newDist);
                        path[next] = v;
                    }
                }
            }
        }
    }

## Bellman-Ford最短路径算法 ##

Bellman-Ford算法能够用于负权图, (Dijstra算法则不能), 且逻辑较为简单, 但其时间复杂度更高.

### BellmanFord.java ###

/****************************************************************************** * Compilation: javac BellmanFord.java * Execution: java BellmanFord * Author: Chenghao Wang ******************************************************************************/
    
    public class BellmanFord extends SP { 
    
        BellmanFord() {  }
        BellmanFord(EdgeWeightedDigraph g, int s) { 
            super(g, s);
            
            for (int i = 0; i < g.V(); i++) { 
                for (WeightedDirectedEdge e : g.edges()) { 
                    if (dist[e.from()] == Double.POSITIVE_INFINITY) { 
                        continue;
                    }
                    else if (dist[e.to()] > (dist[e.from()] + e.weight())) { 
                        dist[e.to()] = dist[e.from()] + e.weight();
                        path[e.to()] = e.from();
                    }
                }
            }
        }
    }

## 算法比较 ##

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>时间复杂度</th> 
   <th>适用场合</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Dijkstra</td> 
   <td><em>Elog(V)</em></td> 
   <td>仅正权图</td> 
  </tr> 
  <tr> 
   <td>Bellman-Ford</td> 
   <td><em>EV</em></td> 
   <td>所有图都可以</td> 
  </tr> 
 </tbody> 
</table>