java我正在尝试求解最短路径的Dijkstra算法。我知道这是不对的，但我该怎么做才能让它起作用呢？

Question

计算从起点到目标的边加权最短路径 使用从任何顶点到目标的最小距离启发式 以减少搜索过程中访问的顶点数

weightMapper提供了一个函数，通过该函数可以检索或计算边的权重 返回从起点到目标的最短路径， 如果开始或目标无法与图形中的顶点匹配，则返回null 或者找不到从开始到目标的路径

public DGPath dijkstraShortestPath(String startId, String targetId,
                                       Function<E, Double> weightMapper) {
        V start = this.getVertexById(startId);
        V target = this.getVertexById(targetId);
        if (start == null || target == null) return null;

        // initialise the result path of the search
        DGPath path = new DGPath();
        path.start = start;
        path.visited.add(start);

        // easy target
        if (start == target) return path;

        // keep track of the DSP status of all visited nodes
        // you may choose a different approach of tracking progress of the algorith, if you wish
        Map<V, DSPNode> progressData = new HashMap<>();

        // initialise the progress of the start node
        DSPNode nextDspNode = new DSPNode(start);
        nextDspNode.weightSumTo = 0.0;
        nextDspNode.marked = true;
        progressData.put(start, nextDspNode);

        Map<V, E> visitedEdges = new HashMap<>(); // visitedEdges of a certain vertex
        visitedEdges.put(start, null); // we start with source as visited vertex without edge

        while (nextDspNode != null) {

            /*
             * continue Dijkstra's algorithm to process nextDspNode
             * mark nodes as you complete their processing
             * register all visited vertices while going for statistical purposes
             * if you hit the target: complete the path and bail out !!!
             */


            for (E edge : nextDspNode.vertex.getEdges()) {
                V neighbour = edge.getTo();
                DSPNode neighbourNode = new DSPNode(neighbour);
                double weight = weightMapper.apply(edge);
                double distanceFromNextNode = nextDspNode.weightSumTo + weight;
                if (distanceFromNextNode < neighbourNode.weightSumTo) {
                    neighbourNode.weightSumTo = distanceFromNextNode;
                    neighbourNode.fromEdge = edge;
                    neighbourNode.marked = true;
                    progressData.put(neighbour, neighbourNode);
                }

                /*
                 find the next nearest node that is not marked yet
                //  nextDspNode = progressData.values().stream()...
                 */
            }
            if (nextDspNode.vertex == target) break;
            nextDspNode = progressData.values().stream().filter(dspNode -> !dspNode.marked).reduce((o1, o2) -> {
                int compare = Double.compare(o1.weightSumTo, o2.weightSumTo);
                if (compare > 0) return o1;
                else if (compare < 0) return o2;
                else return o1;
            }).orElse(null);
        }

        path.totalWeight = progressData.values().stream().mapToDouble(value -> value.weightSumTo).sum();

        // no path found, graph was not connected ???
        return path;
    }

在dijkstra最短路径算法中注册顶点状态的助手类

// helper class to register the state of a vertex in dijkstra shortest path algorithm
private class DSPNode implements Comparable<DSPNode> {
    public V vertex;                // the graph vertex that is concerned with this DSPNode
    public E fromEdge = null;        // the edge from the predecessor's vertex to this node's vertex
    public boolean marked = false;  // indicates DSP processing has been marked complete
    public double weightSumTo = Double.MAX_VALUE;   // sum of weights of current shortest path to this node's vertex

    public DSPNode(V vertex) {
        this.vertex = vertex;
    }

    // comparable interface helps to find a node with the shortest current path, sofar
    @Override
    public int compareTo(DSPNode dspv) {
        return Double.compare(this.weightSumTo, dspv.weightSumTo);
    }
}

Here are the expected results

    @Test
    void checkDSPSearch() {
        DirectedGraph.DGPath path = europe.dijkstraShortestPath("UK", "LUX", b -> 2.0);
        assertNotNull(path);
        assertEquals(europe.getVertexById("UK"), path.getStart());
        assertEquals(4.0, path.getTotalWeight(), 0.0001);
        assertEquals(path.getTotalWeight(), 2.0 * path.getEdges().size(), 0.0001);
        assertTrue(path.getVisited().size() > path.getEdges().size());
    }