расчет алгоритма кратчайшего пути

Question

, так что вопрос будет следующим: Вы получите ориентированный граф G = (V, E) и весовую функцию wt: E-> R +. Вам также даны два выделенных узла s, t ∈ V Напишите алгоритм, который отмечает каждый узел v таким образом, что v лежит на кратчайшем пути от s до t. Введем логическое поле по адресу для каждого узла v. Ваш алгоритм должен установить пост-состояние: ∀ v ∈ V: v. по адресу ≡ (∃ p: shpath (p, s, t) ∩ вдоль (v, p)) где мы определяем shpath (p, s, t) = path (p, s, t) ∩ wt (p) = δ (s, t) и вдоль (v, p) = (v = hd (p) ∪ вдоль (v, tl (p))). Здесь hd, tl обозначают голову и хвост последовательности. Также вдоль (v, λ) = false, где λ - пустая последовательность. Докажите, что ваш алгоритм заканчивается во времени O (| V |^3), с вышеуказанным постусловием true

Я пытался понять это, но есть некоторые вещи, которые я не совсем понимаю, например, мы предполагаем, что существует несколько кратчайших путей? и должен ли мы найти кратчайший путь, а затем посмотреть, какие узлы принадлежат этому пути? или мы должны найти эти узлы, пока мы находимся в процессе поиска кратчайшего пути? и как я должен доказать, что этот алгоритм заканчивается во времени O (| V |^3), пожалуйста, помогите ...

Answer 1

Мы предполагаем, что существует несколько кратчайших путей?

Может быть много кратчайших путей, да. Рассмотрим такой график, как

* * * * 
/\/\/\/\ 
s * * * t 
\/\/\/\/
    * * * * 

где каждое ребро имеет длину 1. Имеются 16 кратчайших путей от s до t.

и должен ли мы найти кратчайший путь, а затем посмотреть, какие узлы принадлежат этому пути?

Если вы попробуете это на приведенном выше графике, вы не сможете пометить 4 узла.

или мы должны найти эти узлы, пока мы находимся в процессе нахождения кратчайшего пути?

Возможно, возможно нет. Существует несколько правильных алгоритмов.

и как я должен доказать, что этот алгоритм оканчиваются время O (| V |^3)

Вы должны беспокоиться о доказательстве правильности первого.