修改Dijkstra以保存具有相同值的路径 - StackOverflow错误

Question

我试图修改Dijkstra的算法以显示所有具有最小值的路径。所以我决定使用以前的顶点列表。我添加了一个if子句，用于检查路径是否为具有最小值的前一个值，并将前一个顶点添加为当前父元素的父元素。 问题是我得到一个StackOverflow错误，我不知道是什么导致它。 这是我的代码： 下面的代码的目的是为图中的所有顶点计算Dijkstra，计算顶点出现在最小路径中的次数，并按降序显示它们全部。

public class Dijkstra { 

    public static final Map<String, Integer> ordem = new HashMap<>(); 

    public static void main(String[] args) throws FileNotFoundException, IOException { 
     List<Graph.Edge> edges = new ArrayList<>(); 

     try { 
      FileReader arq = new FileReader("input.txt"); 
      BufferedReader fw = new BufferedReader(arq); 
      String linha = ""; 
      while (fw.ready()) { 
       linha = fw.readLine(); 
       if (!linha.equals("0,0,0")) { 
        String parts[] = linha.split(","); 
        ordem.put(parts[0], 0); 
        ordem.put(parts[1], 0); 
        Graph.Edge a = new Graph.Edge(parts[0], parts[1], 100 - Integer.parseInt(parts[2])); 
        edges.add(a); 
       } else { 
        break; 
       } 

      } 
      fw.close(); 
     } catch (FileNotFoundException e) { 
      e.printStackTrace(); 
     } 
     Graph g = new Graph(edges); 

     for (int i = 0; i < 5; i++) { 
      g.dijkstra(String.valueOf(i)); 
      g.printAllPaths(); 
     } 

     Object[] a = ordem.entrySet().toArray(); 
     Arrays.sort(a, new Comparator() { 
      public int compare(Object o1, Object o2) { 
       return ((Map.Entry<String, Integer>) o2).getValue() 
         .compareTo(((Map.Entry<String, Integer>) o1).getValue()); 
      } 
     }); 
     for (Object e : a) { 
      System.out.print(((Map.Entry<String, Integer>) e).getKey() + " "); 
     } 
     System.out.println("\n"); 
    } 
} 

class Graph { 

    private final Map<String, Vertex> graph; 

    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; 
     } 
    } 

    public static class Vertex implements Comparable<Vertex> { 

     public final String name; 
     public int dist = Integer.MAX_VALUE; 
     public List<Vertex> previous = new ArrayList<>(); 
     public final Map<Vertex, Integer> neighbours = new HashMap<>(); 

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

     private void printPath() { 
      if (this == this.previous) { 
      } else if (this.previous == null) { 
      } else { 
       //This is where I am getting the error 
       for (int i = 0; i<this.previous.size(); i++){ 
       this.previous.get(i).printPath(); 
       Dijkstra.ordem.replace(this.name, Dijkstra.ordem.get(this.name) + 1); 
      } 

      } 
     } 

     public int compareTo(Vertex other) { 
      if (dist == other.dist) { 
       return name.compareTo(other.name); 
      } 

      return Integer.compare(dist, other.dist); 
     } 

     @Override 
     public String toString() { 
      return "(" + name + ", " + dist + ")"; 
     } 
    } 

    public Graph(List<Graph.Edge> edges) { 
     graph = new HashMap<>(edges.size()); 

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

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


    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<>(); 

     // Inicializacao dos vertices 
     for (Vertex v : graph.values()) { 
      //v.previous = v == source ? list : null; 
      if (v == source) { 
       v.previous.add(source); 
      } else { 
       v.previous = new ArrayList<>(); 
      } 
      v.dist = v == source ? 0 : Integer.MAX_VALUE; 
      q.add(v); 
     } 

     dijkstra(q); 
    } 

    private void dijkstra(final NavigableSet<Vertex> q) { 
     Vertex u, v; 
     while (!q.isEmpty()) { 

      u = q.pollFirst(); 
      if (u.dist == Integer.MAX_VALUE) { 
      } 
      for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) { 
       v = a.getKey(); 

       final int alternateDist = u.dist + a.getValue(); 
       if (alternateDist < v.dist) { 
        q.remove(v); 
        v.dist = alternateDist; 
        v.previous.add(u); 
        q.add(v); 
       } else if(alternateDist == v.dist) { 
        v.previous.add(u); 
       } 
      } 
     } 
    } 


    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(); 
    } 

    public void printAllPaths() { 
     for (Vertex v : graph.values()) { 
      v.printPath(); 
     } 
    } 
} 

这是错误：

Exception in thread "main" java.lang.StackOverflowError 
    at Graph$Vertex.printPath(Dijkstra.java:117) 
    at Graph$Vertex.printPath(Dijkstra.java:118) 

Answer 1

作为错误信息已经暗示：你Dijkstra算法不是问题。 问题是printPath（）调用自己。

有可能的罪魁祸首是

if (this == this.previous) {} ... 

你比较Vertex this到List<Vertex> previous。也许你想检查

if (this == this.previous.get(this.previous.size() - 1)) {} ... 

改为。我没有测试这个，因为你的代码是（1）太长了，（2）没有自包含（至少缺少“input.txt”）。