为什么这个lua dijkstra的算法在某些情况下不起作用？

Question

我正在使用此站点的Dijkstra算法代码：qazxsw poi

不幸的是它对当前边缘表不起作用。

当我从35 - > 36删除连接时，我已经确定问题消失了，但它没有解决问题。

https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Lua

我收到

-- Graph definition
local edges = {
  [34] = {[35] = 1,[37] = 1,},
  [35] = {[34] = 1,[36] = 1,[46] = 1,},
  [36] = {[35] = 1,[37] = 1,},
  [37] = {[34] = 1,[36] = 1,},
  [38] = {[46] = 1,},
  [46] = {[35] = 1,[38] = 1,},
}

-- Fill in paths in the opposite direction to the stated edges
function complete (graph)
    for node, edges in pairs(graph) do
        for edge, distance in pairs(edges) do
            if not graph[edge] then graph[edge] = {} end
            graph[edge][node] = distance
        end
    end
end

-- Create path string from table of previous nodes
function follow (trail, destination)
    local path, nextStep = destination, trail[destination]
    while nextStep do
        path = nextStep .. " " .. path
        nextStep = trail[nextStep]
    end
    return path
end

-- Find the shortest path between the current and destination nodes
function dijkstra (graph, current, destination, directed)
    if not directed then complete(graph) end
    local unvisited, distanceTo, trail = {}, {}, {}
    local nearest, nextNode, tentative
    for node, edgeDists in pairs(graph) do
        if node == current then
            distanceTo[node] = 0
            trail[current] = false
        else
            distanceTo[node] = math.huge
            unvisited[node] = true
        end
    end
    repeat
        nearest = math.huge
        for neighbour, pathDist in pairs(graph[current]) do
            if unvisited[neighbour] then
                tentative = distanceTo[current] + pathDist
                if tentative < distanceTo[neighbour] then
                    distanceTo[neighbour] = tentative
                    trail[neighbour] = current
                end
                if tentative < nearest then
                    nearest = tentative
                    nextNode = neighbour
                end
            end
        end
        unvisited[current] = false
        current = nextNode
    until unvisited[destination] == false or nearest == math.huge
    return distanceTo[destination], follow(trail, destination)
end

-- Main procedure
print("Directed:", dijkstra(edges, 34, 38, true))
print("Undirected:", dijkstra(edges, 34, 38, false))

的输出与当前egdes表内容，但当我删除35 - > 36之间的连接，它提供了良好的输出 - inf, 38

为了更容易理解我上传边缘表的图形表示：3, 34 35 46 38

正如你所看到的那样，当我们从34 - > 35 - > 46 - > 38开始时路线是正确的但是我很难过只有当35到36的连接不存在时它才有用。

为什么它不能在我的代码中显示的情况下工作？

Answer 1

这是Dijkstra算法实现的一个例子

https://i.imgur.com/FFF22C1.png