且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

Dijkstra算法在Java中的实现

更新时间:2022-10-27 08:06:47

Instead of initializing the queue Q with all nodes, just initialize it with the source node.

    for (Vertex v : G.vertexes){ // add source to priority queue
        Q.add(G.vertexes[s]);
    }

and then when you iterate over the neighbors, add them to Q

    for (String vertexId : u.neighbours.keySet()) { // see neighbours of
                                                        // vertex extracted
        int vertexNum = indexForName(G, vertexId);

        Vertex v = G.vertexes[vertexNum];
        int w = weightFunc(G, u, v);

        relax(u, v, w);
        Q.add(v);
    }

New output:

Printing min distance of all vertexes from source vertex A 
Id: C distance: 10
Id: A distance: 0
Id: F distance: 12
Id: G distance: 10
Id: B distance: 5
Id: E distance: 8
Id: D distance: 10

相关阅读

技术问答最新文章