一段代码如何影响算法？

Question

抱歉，如果这是一个愚蠢或错误的问题，我在 Java 中找到了短路径算法的解决方案。这是代码：

import java.io.*;
import java.util.*;

public class Dijkstra {
   private static final Graph.Edge[] GRAPH = {
      new Graph.Edge("a", "b", 7),
      new Graph.Edge("a", "c", 9),
      new Graph.Edge("a", "f", 14),
      new Graph.Edge("b", "c", 10),
      new Graph.Edge("b", "d", 15),
      new Graph.Edge("c", "d", 11),
      new Graph.Edge("c", "f", 2),
      new Graph.Edge("d", "e", 6),
      new Graph.Edge("e", "f", 9),
   };
   private static final String START = "a";
   private static final String END = "e";

   public static void main(String[] args) {
      Graph g = new Graph(GRAPH);
      g.dijkstra(START);
      g.printPath(END);
      //g.printAllPaths();
   }
}

class Graph {
   private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges

   /** One edge of the graph (only used by Graph constructor) */
   public static class Edge {
      public final String v1, v2;
      public final int dist;
      public Edge(String v1, String v2, int dist) {
         this.v1 = v1;
         this.v2 = v2;
         this.dist = dist;
      }
   }

   /** One vertex of the graph, complete with mappings to neighbouring vertices */
   public static class Vertex implements Comparable<Vertex> {
      public final String name;
      public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
      public Vertex previous = null;
      public final Map<Vertex, Integer> neighbours = new HashMap<>();

      public Vertex(String name) {
         this.name = name;
      }

      private void printPath() {
         if (this == this.previous) {
            System.out.printf("%s", this.name);
         } else if (this.previous == null) {
            System.out.printf("%s(unreached)", this.name);
         } else {
            this.previous.printPath();
            System.out.printf(" -> %s(%d)", this.name, this.dist);
         }
      }

      public int compareTo(Vertex other) {
         return Integer.compare(dist, other.dist);
      }
   }

   /** Builds a graph from a set of edges */
   public Graph(Edge[] edges) {
      graph = new HashMap<>(edges.length);

      //one pass to find all vertices
      for (Edge e : edges) {
         if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
         if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
      }

      //another pass to set neighbouring vertices
      for (Edge e : edges) {
         graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
         //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
      }
   }

   /** Runs dijkstra using a specified source vertex */ 
   public void dijkstra(String startName) {
      if (!graph.containsKey(startName)) {
         System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
         return;
      }
      final Vertex source = graph.get(startName);
      NavigableSet<Vertex> q = new TreeSet<>();

      // set-up vertices
      for (Vertex v : graph.values()) {
         v.previous = v == source ? source : null;
         v.dist = v == source ? 0 : Integer.MAX_VALUE;
         q.add(v);
      }

      dijkstra(q);
   }

   /** Implementation of dijkstra's algorithm using a binary heap. */
   private void dijkstra(final NavigableSet<Vertex> q) {      
      Vertex u, v;
      while (!q.isEmpty()) {

         u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
         if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable

         //look at distances to each neighbour
         for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
            v = a.getKey(); //the neighbour in this iteration

            final int alternateDist = u.dist + a.getValue();
            if (alternateDist < v.dist) { // shorter path to neighbour found
               q.remove(v);
               v.dist = alternateDist;
               v.previous = u;
               q.add(v);
            } 
         }
      }
   }

   /** Prints a path from the source to the specified vertex */
   public void printPath(String endName) {
      if (!graph.containsKey(endName)) {
         System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
         return;
      }

      graph.get(endName).printPath();
      System.out.println();
   }
   /** Prints the path from the source to every vertex (output order is not guaranteed) */
   public void printAllPaths() {
      for (Vertex v : graph.values()) {
         v.printPath();
         System.out.println();
      }
   }
}

我理解了这个算法的大部分内容，但是方法 private void dijkstra(final NavigableSet<Vertex> q) 让我对以下问题感到困惑：

由于它没有任何 return 方法，其余代码如何评估它？
使用 NavigableSet / TreeSet 是否比使用 PriorityQueue 更好？

而且，我还有一个关于在 class Vertex 中覆盖的 compareTo 方法的问题，它是如何被调用的？

谢谢

Answer 1

由于它没有任何 return 方法，其余代码如何评估它？

该方法的参数是一个可变容器，它被算法的各个部分引用。

 final Vertex source = graph.get(startName);
  NavigableSet<Vertex> q = new TreeSet<>();

  // set-up vertices
  for (Vertex v : graph.values()) {
     v.previous = v == source ? source : null;
     v.dist = v == source ? 0 : Integer.MAX_VALUE;
     q.add(v);
  }

  dijkstra(q);

使用 NavigableSet / TreeSet 是否比使用 PriorityQueue 更好？你可以在这个问题中找到答案Difference between PriorityQueue and TreeSet in Java?

Answer 2

1) 有两个同名方法：

public void dijkstra(String startName)
private void dijkstra(final NavigableSet<Vertex> q)

如果你调用dijkstra("a")，第一个方法会被调用，如果你调用diijkstra(q)，其中q是一个NavigableSet<Vertex>，那么第二个方法会被调用打电话。

2) 这取决于用于实现TreeSet和PriorityQueue的底层数据结构，以及输入Graph。对于某些输入图，未排序的数组可能比最小堆执行得更快。

3) 我怀疑添加到 NavigableSet 的对象需要有一个有效的 compareTo() 方法，这样 NavigableSet 才能发挥它的魔力。

Answer 3

其余代码如何评估它，因为它没有任何 return 方法？

具体做评价的部分是：

u = q.pollFirst();

影响q.pollFirst() return的部分是：

if (alternateDist < v.dist) { // shorter path to neighbour found
    q.remove(v);
    v.dist = alternateDist;
    v.previous = u;
    q.add(v);
}

v 节点从集合中删除，它的距离正在更新，然后重新添加到集合中。

正在更新的距离是最重要的部分。

可能需要删除然后重新添加的节点，以便节点按新的距离值而不是旧的距离值排序。

所有的点就是q.pollFirst() return距离最短的节点。

使用 NavigableSet / TreeSet 是否比使用 PriorityQueue 更好？

"better" 是主观的。您在寻找速度或更好的界面，还是特定的数据结构？

据我了解，TreeSet 和 PriorityQueue 都使用 Comparable 对节点进行排序，因此从这个意义上讲，它们的工作方式相似。

此外，TreeSet是一个集合，所以节点只能在集合中存在一次，而PriorityQueue是一个队列，可以多次插入相同的节点。

在这种情况下，一个集合似乎适用于 dijkstra 算法。

在class Vertex中覆盖的compareTo方法是如何被调用的？

compareTo 函数由 TreeSet 在内部使用，以便在添加节点时对其进行排序。

将新节点与集合中已有的节点进行比较。 Vertex#compareTo 提供了一种算法来确定两个 Vertex 如何相互比较。在这种情况下，比较Vertex的距离值。

这也暗示了为什么节点被删除并重新添加到 dijkstra(final NavigableSet<Vertex> q) 函数中的集合。

一段代码如何影响算法？

How is a section of code affecting the algorithm?

java

algorithm

priority-queue

treeset