Путаница с графом кратчайшего пути

Я хочу рассчитать кратчайший путь от A до F на этом графике введите здесь описание изображения

Следуя алгоритму Дейкстры, я достигаю E, а затем иду к C, но потом не могу вернуться к E, как мне решить эту проблему?

Мои шаги были:

  • Все стоят до бесконечности, кроме одного, который я установил на 0.
  • Из A я обновил b и c, учитывая, что b стоил 26, я перешел к b.
  • Затем d, e и, наконец, c

graph shortest-path dijkstra
person Carlos Pereira    schedule 21.06.2015    source источник
comment
С алгоритмом Дейкстры вы помните каждое место, где вы были. Итак, как только вы обнаружите, что были в E и C, следующий самый простой способ добраться до.... Но разве вы не должны добраться до C до E?   -  person Teepeemm    schedule 21.06.2015
comment
@Teepeemm Сначала я пошел к B, потому что это было дешевле, чем переход к C, а затем я пошел по пути оттуда. Я что-то упускаю?   -  person Carlos Pereira    schedule 21.06.2015

Ответы (1)


arrow_upward
1
arrow_downward

Похоже, вы выбираете кратчайший путь из того места, где вы сейчас находитесь, и не рассчитываете общее расстояние, чтобы добраться до узла. Давайте подробно рассмотрим это.

Алгоритм Дейкстры устанавливает два набора узлов: посещенные (с известными расстояниями) и непосещенные (с предварительными расстояниями). Мы начинаем с:

visited: { }
unvisited: { a(dist 0), b(dist ∞), c(dist ∞), d(dist ∞), e(dist ∞), f(dist ∞) }

Наименьшее предварительное расстояние становится постоянным, и этот узел является «текущим» узлом. Используя текущий узел, мы обновляем предварительные расстояния, которые текущий узел может достичь на более коротком расстоянии, и помечаем текущий узел как посещенный:

visited: { a(0) }
unvisited: { b(26), c(50), d(∞), e(∞), f(∞) }

Мы повторяем приведенный выше абзац, делая кратчайшее предварительное расстояние постоянным и обновляя ориентировочные расстояния, которые текущий узел может достичь на более коротком расстоянии, и помечаем текущий узел как посещенный:

visited: { a(0), b(26) }
unvisited: { c(50), d(91), e(∞), f(∞) }

И опять:

visited: { a(0), b(26), c(50) }
unvisited: { d(91), e(76), f(∞) }

На этот раз мы выбираем e в качестве текущего узла, потому что его ориентировочное расстояние меньше, чем d. Но предварительное расстояние d не обновляется, потому что мы уже нашли лучшее расстояние. Марк e посетил:

visited: { a(0), b(26), c(50), e(76) }
unvisited: { d(91), f(101) }

Теперь d является текущим, но никакие расстояния он не обновляет (нам не нужно смотреть на посещенные узлы, мы уже нашли там лучшие расстояния). Поэтому мы просто отмечаем его как посещенный:

visited: { a(0), b(26), c(50), e(76), d(91) }
unvisited: { f(101) }

Теперь f является текущим, что означает, что мы закончили.

person Teepeemm    schedule 21.06.2015
comment
спасибо за длинное и подробное объяснение! Единственное, что меня все еще беспокоит, это то, как мы идем от узла b к узлу c, в то время как между ними нет никакой связи... - person Carlos Pereira; 21.06.2015
comment
Мы не переходим от b к c. Мы рассматриваем все возможные расстояния до c. В частности, когда a является текущим, мы используем его для обновления ориентировочного расстояния до c (поэтому мы переходим от a к c). Ничто другое не меняет это предварительное расстояние, поэтому к тому времени, когда c становится текущим, это расстояние становится постоянным. - person Teepeemm; 21.06.2015
comment
о хорошо, это имеет смысл! А где вы храните кратчайший путь? последовательность узлов, которая дает вам кратчайший путь между одним узлом и другим? - person Carlos Pereira; 21.06.2015
comment
Всякий раз, когда вы записываете/обновляете расстояние, вы можете записать путь, который дает вам это расстояние. - person Teepeemm; 21.06.2015
comment
тогда хорошо, спасибо за терпение и за невероятно хорошую информацию! Ваше здоровье - person Carlos Pereira; 21.06.2015