Dijkstra的算法--为什么每次提取优先级最小的顶点？

Question

我正在学习Dijkstra的算法来寻找最短路径。我注意到有一个优先级队列来帮助提取顶点集中优先级最低的顶点。如果我从顶点集中选择一个顶点，而不是优先级最低的顶点，那么该算法是否仍然有效?如果是，那么时间复杂度如何？

维基百科最初的Dijkstra算法如下：

function Dijkstra(Graph, source):
    dist[source] ← 0                                

    create vertex set Q

    for each vertex v in Graph:           
        if v ≠ source
            dist[v] ← INFINITY                      
            prev[v] ← UNDEFINED                     

    Q.add_with_priority(v, dist[v])


    while Q is not empty:                          
        u ← Q.extract_min()                        
        for each neighbor v of u:                  
            alt ← dist[u] + length(u, v) 
            if alt < dist[v]
                dist[v] ← alt
                prev[v] ← u
                Q.decrease_priority(v, alt)

    return dist[], prev[]

修改后，无论优先级如何选择顶点(，请注意，松弛后有一个“添加”，)：

function DijkstraVariant(Graph, source):
    dist[source] ← 0                                

    create vertex set Q

    for each vertex v in Graph:           
        if v ≠ source
            dist[v] ← INFINITY                      
            prev[v] ← UNDEFINED                     

    Q.just_add(v)                  // Don't care about the priority


    while Q is not empty:                          
        u ← Q.random_pick()         // Don't care about the priority        
        for each neighbor v of u:                 
            alt ← dist[u] + length(u, v) 
            if alt < dist[v]
                dist[v] ← alt
                prev[v] ← u
                Q.just_add(v)  // Don't care about the priority

    return dist[], prev[]

Answer 1

不，这不管用。它将产生一条道路，但它不再保证是最短的。

优先级要求考虑非均匀权值，对于普通FIFO队列，只有在所有边权相等的情况下才能工作。它成为一个普通的广泛的第一次搜索。

该算法通过随机选择代替优先级，进一步降低到深度优先搜索的水平。这也消除了BFS提供的所有保证，比如在有限时间内在无限图中找到任何存在的路径。