0

有人可以帮我实现吗？我陷入了无限循环，但我不知道为什么。我认为问题出在我寻找具有最小距离的节点的步骤中......我真的很感激这方面的一些帮助。

import java.util.*;

public class Dijkstra {
private Map<String, Integer> dist;
private Set<Vertex> unvisited;
//private Set<Vertex> processed;
private Vertex source;
private Graph g;

public Dijkstra(Graph g, Vertex source) {
    this.g = g;
    this.source = source;
    //dist = new int[g.numOfVertices()];
    dist = new HashMap<String, Integer>();
    for(Vertex v: g.getVertices()) {
        if (v == this.source)
            dist.put(v.getId(), 0);
        else
            dist.put(v.getId(), Integer.MAX_VALUE);
    }
    unvisited = new HashSet<Vertex>(); 
    for(int i = 1; i < g.numOfVertices(); i++) {
        unvisited.add(g.getVertices().get(i));
    }       
}

public ArrayList<Integer> getShortestPaths() {
    while (!unvisited.isEmpty()) {
        Vertex current = this.getMinimum();
        System.out.println("Hello1");
        unvisited.remove(current);
        System.out.println("Hello2: "+ current.getId());
        if (dist.get(current.getId()) == Integer.MAX_VALUE)
            break;
        Map<Vertex,Integer > neighbors = new HashMap<Vertex,Integer>();
        for (Edge e : g.getEdges()) {
            if (e.getSource().getId() == current.getId() && unvisited.contains(e.getDestination())) {
                neighbors.put(e.getDestination(), e.getWeight());
            }
        }
        for (Vertex v : neighbors.keySet()) {
            int alt = dist.get(current.getId()) + neighbors.get(v);
            if (alt < dist.get(v.getId())) {
                dist.put(v.getId(), alt);
            }
        }           
    }





    return new ArrayList<Integer> (dist.values());//(ArrayList<Integer>) dist.values();
}

public Vertex getMinimum() {
    int indexOfMinimum = -1;
    //String indexOfMinimum = "";
    int minimum = Integer.MAX_VALUE;
    for (String i : dist.keySet() ) {
        if (dist.get(i) < minimum) {
            minimum = dist.get(i);
            System.out.println(minimum);
            indexOfMinimum = Integer.parseInt(i);
        }
    }
    return g.getVertices().get(indexOfMinimum);
}




public static void main(String[] args) {
    System.out.println("Hello World!!!");
    List<Vertex> v = new ArrayList<Vertex>();
    List<Edge> e = new ArrayList<Edge>();
    v.add(new Vertex("0"));
    v.add(new Vertex("1"));
    v.add(new Vertex("2"));
    v.add(new Vertex("3"));
    Graph g = new Graph(v ,e);
    g.addEdge(v.get(0), v.get(3), 1);
    g.addEdge(v.get(0), v.get(2), 4);
    g.addEdge(v.get(3), v.get(2), 2);
    g.addEdge(v.get(3), v.get(1), 6);
    g.addEdge(v.get(2), v.get(1), 3);
    Dijkstra sp = new Dijkstra(g, v.get(0));
    ArrayList<Integer> dist1 = sp.getShortestPaths();

    for (int i: dist1) { 
        System.out.println("Hello");
        System.out.println(dist1.get(i));
    }
    //v.add(new Vertex("5"));
    //v.add(new Vertex("6"));
    //v.add(new Vertex("7"));

}

}


public class Graph {
private final List<Vertex> vertices;
private final List<Edge> edges;

public Graph(List<Vertex> vertices, List<Edge> edges) {
    this.vertices = vertices;
    this.edges = edges;
}

public List<Vertex> getVertices() {
    return vertices;
}

public List<Edge> getEdges() {
    return edges;
}

public void addEdge(Vertex from, Vertex to, int weight) {
    edges.add(new Edge(from, to, weight));
}

public void addVertex(Vertex v) {
    vertices.add(v);
}

public int numOfVertices() {
    return this.vertices.size();
}

public int numOfEdges() {
    return this.edges.size();
}
}

class Vertex {
final private String id;

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

public String getId() {
    return this.id;
}
}

class Edge {
//private final String id;
private final Vertex source;
private final Vertex destination;
private final int weight;

public Edge(Vertex source, Vertex destination, int weight) {
    this.source = source;
    this.destination = destination;
    this.weight = weight;
}

public Vertex getSource() {
    return this.source;
}

public Vertex getDestination() {
    return this.destination;
}

public int getWeight() {
    return this.weight;
}

}
4

3 回答 3

2

您的数据结构似乎有点混乱。特别是，您似乎没有任何结构可以按顺序实际跟踪需要考虑的节点。dist包括起始节点，它总是在距离 0，所以dist不能是那个数据结构。

我建议从可靠来源的伪代码版本开始，并非常小心地使您的数据结构在名称和含义上完全匹配它。如果您仍然遇到麻烦，请发布对您正在遵循的伪代码的引用以及您的代码。这将使您更容易理解您的意图。

于 2013-08-11T06:31:31.840 回答
1

这可能不是问题，但它是可疑的：

for(int i = 1; i < g.numOfVertices(); i++) {
    unvisited.add(g.getVertices().get(i));
}

你为什么要初始化i = 1？

于 2013-08-11T05:39:30.627 回答
1

你总是设置current = getMinimum()whilegetMinimum()不关心节点是否被访问，所以它总是选择0节点，这就是它循环的原因。更改您的代码，因此getMinimum()必须选择与该节点不同的节点current。您实际上应该有一个堆结构，按距离排序，并且始终 poll() 具有最小值的那个（并且 poll() 我的意思是从容器中取出它）。log(n)在没有getMinimum() 复杂性的情况下实现它不是一个好主意。

于 2013-08-11T09:14:24.380 回答