用Dijkstra最短路径算法设置顶点权重

Question

然而，出现的问题是，当我将一个顶点设置为一个旅游站点并给它一个权重时，该顶点在第一次访问时似乎根本没有权重。然后，当第二次访问顶点时，权重显示出来。我不知道问题出在哪里，但我猜是因为我没有直接编辑原始变量。

打印输出行标记在下面的**之间。一个在calculateShortest（）中，另一个在calculateMin（）中。

public class Graph
{
    protected HashMap<Integer, GraphNode> ntable = new HashMap<Integer, GraphNode>();
    //a hashmap of every node's edge treemap, in which edges are sorted according to weight of each
    protected HashMap<Integer, TreeMap<Integer, GraphEdge>> etable = new HashMap<Integer, TreeMap<Integer,GraphEdge>>();
}

public class GraphNode
{
    private int val;
    private boolean site;
    private boolean hotel;
    private int time;
    private int distance = Integer.MAX_VALUE;
    private LinkedList<GraphNode> shortest = new LinkedList<GraphNode>();
}

public class GraphEdge implements Comparable<GraphEdge>
{
    private int nd1;
    private int nd2;
    private int weight;
}

public class Path
{
    protected LinkedList<GraphNode> path = new LinkedList<GraphNode>();
    Graph g = new Graph();
    GraphNode start = new GraphNode(0);
    protected HashSet<GraphNode> settled = new HashSet<GraphNode>();
    protected HashSet<GraphNode> unsettled = new HashSet<GraphNode>();

    public Graph calculateShortest(int start)
    {
        g.ntable.get(start).setDist(0);
        unsettled.add(g.ntable.get(start));
        while (unsettled.size() != 0)
        {
            GraphNode current = getLowestCostNode(unsettled);
            unsettled.remove(current);
            TreeMap<Integer, GraphEdge> adjacentE = g.etable.get(current.getVal());
            *
           //printing out below shows vertex has no weight
            System.out.println("Curr: "+ current.getVal() + " " + current.getSiteTime());
            *
            for (GraphEdge edge: adjacentE.values())
            {
                GraphNode adjacent = g.ntable.get(edge.getEnd());
                int cost = edge.getWeight() + current.getSiteTime();
                if (!settled.contains(adjacent))
                {
                    calculateMin(adjacent, cost, current);
                    unsettled.add(adjacent);
                }
            }
            settled.add(current);
        }
    return g;
}

    public GraphNode getLowestCostNode(HashSet<GraphNode> unsettled)
    {
        GraphNode lowestDistNd = null;
        int lowestDist = Integer.MAX_VALUE;
        for (GraphNode nd : unsettled)
        {
            int nodeDist = nd.getDist();
            if (nodeDist < lowestDist)
            {
                lowestDist = nodeDist;
                lowestDistNd = nd;
            }
        }
        return lowestDistNd;
    }

    public void calculateMin(GraphNode evaNd, int cost, GraphNode startNd)
    {
        int startDist = startNd.getDist();
        if (startDist + cost < evaNd.getDist())
        {
            evaNd.setDist(startDist + cost);
            LinkedList<GraphNode> shortest = new LinkedList<GraphNode>(startNd.getShortest());
            shortest.add(startNd);
            evaNd.setShortest(shortest);
            *
            //print out if the node's distance is changed
            System.out.println("Change " + evaNd.getVal() + " " + evaNd.getDist());
            *
        }
    }
}

显示问题的行打印输出（不包括main方法输出）：

Curr: 1 0
Change: 2 10
Change: 3 15
Curr: 2 0
Change: 4 22
Change: 6 25
Curr: 3 0
Change: 5 25
Curr: 4 0 //1st time visiting shows no weight
Change: 6 23
Change: 5 24
Curr: 6 0
Curr: 5 0
Curr: 1 0
Curr: 2 0
Curr: 3 0
Curr: 4 30 //2nd time visiting shows weight
Curr: 6 0
Curr: 5 0

public static void main (String [] args){
    Path p = new Path();
    p.g.addNodeEdge(1, 2, 10);
    p.g.addNodeEdge(1, 3, 15);
    p.g.addNodeEdge(2, 4, 12);
    p.g.addNodeEdge(2, 6, 15);
    p.g.addNodeEdge(3, 5, 10);
    p.g.addNodeEdge(4, 6, 1);
    p.g.addNodeEdge(4, 5, 2);
    p.g.addNodeEdge(6, 5, 5); 
    p.calculateShortest(1);
    System.out.println(p.g.ntable.get(5).getDist());//print out 24

    p.settled.clear();
    p.unsettled.clear();
    p.g.ntable.get(4).setSite(30);
    p.calculateShortest(1);  
    System.out.println(p.g.ntable.get(5).getDist());//still print out 24
}

Answer 1

尽管您正在清除已结算和未结算的哈希集，但跟踪到目前为止找到的节点的最短路径的变量是GraphNode实例变量Distance。在第一次运行calculateShortest后，节点5的距离不会从24的值重置，当然，在将节点4的站点时间设置为30后调用该方法后，距离将保持不变。

一个可能的解决方案是更改calculateShortest（）的开头，以重置所有节点距离：

public Graph calculateShortest(int start) {
    for (GraphNode n : g.ntable.values()) {
        n.setDist(Integer.MAX_VALUE);
    }
    g.ntable.get(start).setDist(0);
    ...

另外，花了一些时间来解决这个问题，主要是因为您发布的代码格式化得很差。下次，请避免发布嵌套类，并包含所有潜在的相关实现细节，而不是简单的getter/setter（如addNodeEdge）。你永远不知道那讨厌的虫子可能藏在哪里！