Почему этот алгоритм Луа Дейкстры не работает в некоторых случаях?

Question

Я использую код алгоритма Дейкстры с этого сайта: https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Lua

К сожалению, он не работает для текущей таблицы ребер.

Я определил, что проблема исчезает, когда я удаляю соединение из 35-> 36, но это не решает проблему.

-- 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))

Я получаю вывод inf, 38 с текущим содержимым таблицы egdes, но когда я удаляю соединение между 35 -> 36, это дает хороший вывод -3, 34 35 46 38

Для облегчения понимания я загружаю графическое представление таблицы ребер: https://i.imgur.com/FFF22C1.png

Как вы можете видеть, маршрут идет другим путем, когда мы начинаем с 34 -> 35 -> 46 -> 38 но как мне грустно Это работает только тогда, когда не существует соединения от 35 до 36.

Почему это не работает в случае, показанном в моем коде?

Answer 1

Это пример реализации алгоритма Дейкстры

-- 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,},
}
local starting_vertex, destination_vertex = 34, 38

local function create_dijkstra(starting_vertex)
   local shortest_paths = {[starting_vertex] = {full_distance = 0}}
   local vertex, distance, heap_size, heap = starting_vertex, 0, 0, {}
   return
      function (adjacent_vertex, edge_length)
         if adjacent_vertex then
            -- receiving the information about adjacent vertex
            local new_distance = distance + edge_length
            local adjacent_vertex_info = shortest_paths[adjacent_vertex]
            local pos
            if adjacent_vertex_info then
               if new_distance < adjacent_vertex_info.full_distance then
                  adjacent_vertex_info.full_distance = new_distance
                  adjacent_vertex_info.previous_vertex = vertex
                  pos = adjacent_vertex_info.index
               else
                  return
               end
            else
               adjacent_vertex_info = {full_distance = new_distance, previous_vertex = vertex, index = 0}
               shortest_paths[adjacent_vertex] = adjacent_vertex_info
               heap_size = heap_size + 1
               pos = heap_size
            end
            while pos > 1 do
               local parent_pos = (pos - pos % 2) / 2
               local parent = heap[parent_pos]
               local parent_info = shortest_paths[parent]
               if new_distance < parent_info.full_distance then
                  heap[pos] = parent
                  parent_info.index = pos
                  pos = parent_pos
               else
                  break
               end
            end
            heap[pos] = adjacent_vertex
            adjacent_vertex_info.index = pos
         elseif heap_size > 0 then
            -- which vertex neighborhood to ask for?
            vertex = heap[1]
            local parent = heap[heap_size]
            heap[heap_size] = nil
            heap_size = heap_size - 1
            if heap_size > 0 then
               local pos = 1
               local last_node_pos = heap_size / 2
               local parent_info = shortest_paths[parent]
               local parent_distance = parent_info.full_distance
               while pos <= last_node_pos do
                  local child_pos = pos + pos
                  local child = heap[child_pos]
                  local child_info = shortest_paths[child]
                  local child_distance = child_info.full_distance
                  if child_pos < heap_size then
                     local child_pos2 = child_pos + 1
                     local child2 = heap[child_pos2]
                     local child2_info = shortest_paths[child2]
                     local child2_distance = child2_info.full_distance
                     if child2_distance < child_distance then
                        child_pos = child_pos2
                        child = child2
                        child_info = child2_info
                        child_distance = child2_distance
                     end
                  end
                  if child_distance < parent_distance then
                     heap[pos] = child
                     child_info.index = pos
                     pos = child_pos
                  else
                     break
                  end
               end
               heap[pos] = parent
               parent_info.index = pos
            end
            local vertex_info = shortest_paths[vertex]
            vertex_info.index = nil
            distance = vertex_info.full_distance
            return vertex
         end
      end,
      shortest_paths
end

local vertex, dijkstra, shortest_paths = starting_vertex, create_dijkstra(starting_vertex)
while vertex and vertex ~= destination_vertex do
   -- send information about all adjacent vertexes of "vertex"
   for adjacent_vertex, edge_length in pairs(edges[vertex]) do
      dijkstra(adjacent_vertex, edge_length)
   end
   vertex = dijkstra()  -- now dijkstra is asking you about the neighborhood of another vertex
end
if vertex then
   local full_distance = shortest_paths[vertex].full_distance
   local path = vertex
   while vertex do
      vertex = shortest_paths[vertex].previous_vertex
      if vertex then
         path = vertex.." "..path
      end
   end
   print(full_distance, path)
else
   print"Path not found"
end