Dijkstra的算法模擬

Question

我正在研究Dijkstra的最短路徑算法的實現，以模擬多播路由的工作方式，但是我的仿真類出現錯誤，如果有人能幫助我，我將不勝感激。

模擬類

public class simulation 
{ 
    private List<Vertex> nodes; 
    private List<Edge> edges; 
    public void testExcute() 
    { 
     nodes = new ArrayList<Vertex>(); 
     edges = new ArrayList<Edge>(); 
     for (int i = 0; i < 11; i++) 
     { 
      Vertex location = new Vertex("Node_" + i, "Node_" + i); 
      nodes.add(location); 
     } 
    } 
    addLink("Edge_0", 0, 1, ((int)Math.random()*101)); 
    addLink("Edge_1", 0, 2, ((int)Math.random()*101)); 
    addLink("Edge_2", 0, 4, ((int)Math.random()*101)); 
    addLink("Edge_3", 2, 6, ((int)Math.random()*101)); 
    addLink("Edge_4", 2, 7, ((int)Math.random()*101)); 
    addLink("Edge_5", 3, 7, ((int)Math.random()*101)); 
    addLink("Edge_6", 5, 8, ((int)Math.random()*101)); 
    addLink("Edge_7", 8, 9, ((int)Math.random()*101)); 
    addLink("Edge_8", 7, 9, ((int)Math.random()*101)); 
    addLink("Edge_9", 4, 9, ((int)Math.random()*101)); 
    addLink("Edge_10", 9,10,((int)Math.random()*101)); 
    addLink("Edge_11", 1,10,((int)Math.random()*101)); 

    // Lets check from location Loc_1 to Loc_10 
    Graph graph = new Graph(nodes, edges); 
    DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph); 
    dijkstra.execute(nodes.get(0)); 
    LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10)); 

    for (Vertex vertex : path) 
    { 
     System.out.println(vertex); 
    } 
    public void addLink(String laneId, int outcomingPortLabel, int incomingPortLabel,int cost) 
    { 
    Edge link = new Edge(laneId,nodes.get(outcomingPortLabel), nodes.get(incomingPortLabel), cost); 
    edges.add(link); 
    } 
} 

邊緣種類

package multicastroutingproject; 
public class Edge 
{ 
    private final String id; 
    private final Vertex source; 
    private final Vertex destination; 
    private final int weight; 

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

    public String getId() 
    { 
     return id; 
    } 
    public Vertex getDestination() 
    { 
     return destination; 
    } 
    public Vertex getSource() 
    { 
     return source; 
    } 
    public int getWeight() 
    { 
     return weight; 
    } 
    @Override 
    public String toString() 
    { 
    return source + " " + destination; 
    } 
} 

Graph類

package multicastroutingproject; 
import java.util.List; 
public class Graph 
{ 
    private final List<Vertex> vertexes; 
    private final List<Edge> edges; 
    public Graph(List<Vertex> vertexes, List<Edge> edges) 
    { 
     this.vertexes = vertexes; 
     this.edges = edges; 
    } 
    public List<Vertex> getVertexes() 
    { 
     return vertexes; 
    } 
    public List<Edge> getEdges() 
    { 
     return edges; 
    } 
} 

頂點類

package multicastroutingproject; 
public class Vertex 
{ 
    final private String id; 
    final private String name; 
    public Vertex(String id, String name) 
    { 
     this.id = id; 
     this.name = name; 
    } 
    public String getId() 
    { 
     return id; 
    } 

    public String getName() 
    { 
     return name; 
    } 

    @Override 
    public int hashCode() 
    { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((id == null) ? 0 : id.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) 
    { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     Vertex other = (Vertex) obj; 
     if (id == null) { 
      if (other.id != null) 
       return false; 
     } 
     else if (!id.equals(other.id)) 
      return false; 
    return true; 
    } 

    @Override 
    public String toString() 
    { 
     return name; 
    } 
} 

最後Dijkstra的類

package multicastroutingproject; 
import java.util.*; 
public class DijkstraAlgorithm 
{ 
    private final List<Vertex> nodes; 
    private final List<Edge> edges; 
    private Set<Vertex> settledNodes; 
    private Set<Vertex> unSettledNodes; 
    private Map<Vertex, Vertex> predecessors; 
    private Map<Vertex, Integer> distance; 
    public DijkstraAlgorithm(Graph graph) 
    { 
    // create a copy of the array so that we can operate on this array 
    this.nodes = new ArrayList<>(graph.getVertexes()); 
    this.edges = new ArrayList<>(graph.getEdges()); 
    } 
    public void execute(Vertex source) 
    { 
    settledNodes = new HashSet<Vertex>(); 
    unSettledNodes = new HashSet<Vertex>(); 
    distance = new HashMap<Vertex, Integer>(); 
    predecessors = new HashMap<Vertex, Vertex>(); 
    distance.put(source, 0); 
    unSettledNodes.add(source); 
    while (unSettledNodes.size() > 0) 
    { 
     Vertex node = getMinimum(unSettledNodes); 
     settledNodes.add(node); 
     unSettledNodes.remove(node); 
     findMinimalDistances(node); 
    } 
    } 
    private void findMinimalDistances(Vertex node) 
    { 
    List<Vertex> adjacentNodes = getNeighbors(node); 
    for (Vertex target : adjacentNodes) 
    { 
     if (getShortestDistance(target) > getShortestDistance(node) 
      + getDistance(node, target)) 
     { 
     distance.put(target, getShortestDistance(node) 
      + getDistance(node, target)); 
     predecessors.put(target, node); 
     unSettledNodes.add(target); 
     } 
    } 
    } 
    private int getDistance(Vertex node, Vertex target) 
    { 
    for (Edge edge : edges) 
    { 
     if (edge.getSource().equals(node) 
      && edge.getDestination().equals(target)) 
     { 
     return edge.getWeight(); 
     } 
    } 
    throw new RuntimeException("Should not happen"); 
    } 
    private List<Vertex> getNeighbors(Vertex node) 
    { 
    List<Vertex> neighbors = new ArrayList<Vertex>(); 
    for (Edge edge : edges) 
    { 
     if (edge.getSource().equals(node) 
      && !isSettled(edge.getDestination())) 
     { 
     neighbors.add(edge.getDestination()); 
     } 
    } 
    return neighbors; 
    } 
    private Vertex getMinimum(Set<Vertex> vertexes) 
    { 
    Vertex minimum = null; 
    for (Vertex vertex : vertexes) 
    { 
     if (minimum == null) 
     { 
     minimum = vertex; 
     } 
     else 
     { 
     if (getShortestDistance(vertex) < getShortestDistance(minimum)) 
     { 
      minimum = vertex; 
     } 
     } 
    } 
    return minimum; 
    } 
    private boolean isSettled(Vertex vertex) 
    { 
    return settledNodes.contains(vertex); 
    } 
    private int getShortestDistance(Vertex destination) 
    { 
    Integer d = distance.get(destination); 
    if (d == null) 
    { 
    return Integer.MAX_VALUE; 
    } 
    else 
    { 
     return d; 
    } 
} 
public LinkedList<Vertex> getPath(Vertex target) 
{ 
    LinkedList<Vertex> path = new LinkedList<Vertex>(); 
    Vertex step = target; 
    // check if a path exists 
    if (predecessors.get(step) == null) 
    { 
    return null; 
    } 
    path.add(step); 
    while (predecessors.get(step) != null) 
    { 
    step = predecessors.get(step); 
    path.add(step); 
    } 
    // Put it into the correct order 
    Collections.reverse(path); 
    return path; 
    } 
} 

當我嘗試

addLink("Edge_9", 4, 9, ((int)Math.random()*101));

它給了我下面的警告/錯誤：「無效的方法聲明，缺少返回類型」，並建議我重新命名addLink添加到模擬，這是沒有意義的。

其他警告/錯誤我得到的線

DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph); 
dijkstra.execute(nodes.get(0)); 

它說，包Dijkstra算法不存在，但我很清楚的實例在obove線路的對象。

最後，

LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10)); 

for (Vertex vertex : path) 
{ 
    System.out.println(vertex); 
} 

這一次它說「式的非法的開始」，並建議我創造我的包「路徑」類，但同樣沒有任何意義，因爲我實例化路徑正好在每個循環之上。

對於這篇長文章我很抱歉，但有人知道我爲什麼會收到這些錯誤 ？

Answer 1

那裏有幾個問題，但最明顯的是，您撥打addLink()的電話是在課程正文中間，而不是在方法中。編譯器期望在那裏有一個方法聲明，並不知道如何處理這些調用。 看來你錯過了main()。您應該查看一些Java語法。