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

Question

新 java。

我想要制作的是一个代表城市的有向图。大多数顶点只是街道，但一些是具有权重的旅游景点（因为一个人必须在那里停留一段时间）。我正在使用 Dijkstra 的 最短路径算法 并制作了一些用于将顶点权重添加到其中的版本。

但是，问题出现了，当我将一个顶点设置为旅游站点并赋予它权重时，该顶点在第一次访问时似乎根本没有权重.当第二次访问顶点时，权重就会出现。我不知道问题出在哪里，但我猜测它是在我没有直接编辑原始变量的地方。

打印出来的行在下方标记在 * * 之间。一个在 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

对于每个顶点，getDist() return 源顶点到自身的距离，以及 getCost() return 距离加上顶点的权重。

我的主要方法如下。 addNodeEdge() 已经过测试可以正常工作。我正在使用来自 Dijkstra Algorithm in Java 的 示例（见下图） 并且 ABCDEF 在我的例子中是 123456。除了图表之外，我 尝试将 D（即顶点 4）设为权重为 30 的站点。 Visualization of the graph

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
}

我期望到 E（顶点 5）30 和 F（顶点 6）25 的最短路径，因为权重为 30 的通过 D（顶点 4）的路径太大。但是，我改变 D 的权重后得到的结果与我向 D 添加权重之前完全相同。就像我上面解释的那样，我认为问题出在 D 的体重变化上......任何帮助将不胜感激。

Answer 1

即使您正在清除已解决和未解决的 HashSet，跟踪到目前为止找到的节点的最短路径的变量是 GraphNode 实例变量 distance。节点 5 的距离在第一次运行 calculateShortest 后不会从 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);
    ...

此外，我花了一些时间才弄明白这一点，主要是因为您发布的代码格式很差。下次请避免发布嵌套的类，并包括所有重要的潜在相关实现细节 getters/setters（例如 addNodeEdge）。你永远不知道那个讨厌的错误可能藏在哪里！

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

Setting vertex weight with Dijkstra's shortest path algorithm

graph

path

dijkstra

shortest-path

vertex