Как найти кратчайший путь от вершины к другой в графе с помощью алгоритма Дейкстры

Question

Я работаю над проектом TOP, где я должен сделать функцию, которая возвращает кратчайший путь между двумя вершинами графа, но я получаю ошибку.Что я могу сделать, чтобы решить эту проблему?

Ничего еще, потому что я новичок.

класс Graph

class Vertex
  attr_accessor :value, :neighbors, :prev, :dist
  def initialize(value)
      @value = value
      @neighbors = []
      @prev = nil
      @dist = Float::INFINITY
  end

  def add_edge(adjacent_vertex)
      @neighbors << adjacent_vertex
  end
end

class Graph
  attr_reader :vertices
  def initialize
      @vertices = {}
      @dijkstra_source = nil
  end

  def add_vertex(vertex)
      @vertices[vertex.value] = vertex
  end

  def add_edge(vertex1, vertex2)
      @vertices[vertex1.value].add_edge(@vertices[vertex2])
      @vertices[vertex2.value].add_edge(@vertices[vertex1])
  end

  def dijkstra(source)
    return if @dijkstra_source == source
      unvisited = @vertices.values
      unvisited.each do |vertex|
          vertex.dist = Float::INFINITY
          vertex.prev = nil
      end
      @vertices[source].dist = 0
      until unvisited.empty?
          current_node = unvisited.min_by(&:dist)
          break if current_node.dist == Float::INFINITY
          unvisited.delete(current_node)
          current_node.neighbors.each do |v|
              neighbor = @vertices[v]
              if unvisited.include?(neighbor)
                  alt = current_node.dist + 1
                  if alt < neighbor.dist
                    neighbor.dist = alt
                    neighbor.prev = current_node 
                  end
              end
          end
      end
      @dijkstra_source = source
  end

  def find_shortest_path(source, target)
      dijkstra(source)
      path = []
      u = target
      while u
          path.unshift(u)
          u = @vertices[u].prev
      end
      return path
  end
end

Где я устанавливаю вершины

require_relative 'graph'

class Knight
  attr_reader :character, :graph
  def initialize
      @character = "♞"
      @possible_moves = nil
      @positions = Array.new(8) { Array.new(8, " ") }
      @move_set = [
                    [-1,-2],
                    [-2,-1],
                    [-2,+1],
                    [-1,+2],
                    [+1,+2],
                    [+2,+1],
                    [+2,-1],
                    [+1,-2]
                   ]
      @graph = generate_graph
      generate_edges
  end

  def generate_graph
    graph = Graph.new
      @positions.each_index do |x|
          @positions[x].each_index do |y|
              vertex = Vertex.new([x,y])
              graph.add_vertex(vertex)
          end
      end
      graph
  end

  def generate_edges
      @graph.vertices.each do |key, value|
          @move_set.each do |move|
              x = key[0] + move[0]
              y = key[1] + move[1]
              if (0..7).include?(x) && (0..7).include?(y)
                  vertex = [x,y]
                  value.add_edge(vertex) unless value.neighbors.include?(vertex)
              end
          end
      end
  end
end

knight = Knight.new
knight.generate_edges
p knight.graph.find_shortest_path([1,2],[2,3])

Я ожидаю массив, который хранит внутри кратчайшего пути от исходной вершины ([1,2]) до целевой вершины (2,3).

Но вместо этого я получаюОшибка NilClass

Traceback (most recent call last):
    1: from knight.rb:50:in `<main>'
/home/brito/the_odin_project/knight_moves/graph.rb:63:in `find_shortest_path': undefined method `prev' for nil:NilClass (NoMethodError)

Answer 1

Проблема в том, что что-то не было инициализировано (nil) при попытке вызвать для него метод prev, как это видно из сообщения об ошибке.

Ближайший подозрительный звонок в Graph#find_shortest_path. Если вы напечатаете @vertices и u оттуда, вы увидите, что на второй итерации u становится Vertex экземпляром , а @vertices имеет необработанные значения в качестве ключей. Исправление будет состоять в том, чтобы изменить u = @vertices[u].prev на u = @vertices[u].prev.value, чтобы u был необработанным значением (обратите внимание на проверку для @vertices[u].prev в первую очередь.

Подведение итогов:

def find_shortest_path(source, target)
  dijkstra(source)
  path = []
  u = target
  while u
    path.unshift(u)
    u = (@vertices[u].prev.value if @vertices[u].prev)
  end
  return path
end

---

Также приведенный выше код исправит проблему, код не является рубиновым идиоматическим; FWIW, я выложу идиоматическую версию.

Я понимаю, это слишком много необычных шаблонов для вас, но на случай, если вам будет интересно покопаться:

def find_shortest_path(source, target)
  dijkstra(source)

  loop.reduce([[], target]) do |(path, u), _|
    break path unless u
    [
      path << u,
      (@vertices[u].prev.value if @vertices[u].prev)
    ]
  end
end