有人可以帮我实施吗?我陷入无限循环,但我不知道为什么。我认为问题出在我寻找具有最小距离的节点的步骤中……在此,我将非常感谢您的帮助。
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;
}
}
最佳答案
您的数据结构似乎有些混乱。特别是,您似乎没有任何结构可以按顺序实际跟踪需要考虑的节点。 dist
包括起始节点,起始节点始终处于距离0,因此dist
不能是该数据结构。
我建议从可靠来源的伪代码版本开始,并要非常小心以使您的数据结构在名称和含义上完全匹配。如果仍然遇到麻烦,请将对您所遵循的伪代码的引用与代码一起发布。这将使您更容易理解您的意图。
关于java - Dijkstra算法的实现-陷入无限循环,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18169041/