Как использовать массив d и π, чтобы проверить, является ли кратчайший путь от s до t в G уникальным или нет, за O (n log n + m) времени?

Question

Нам дан ориентированный граф G = (V, E) с положительной весовой функцией: w: E → R> 0 и двумя вершинами s, t ∈ V. Предположим, что мы уже вычислили массив d и π с помощью алгоритма Дийкастры: d [v] - длина кратчайшего пути от s до v, а π [v] - вершина перед v в пути.

Как мы используем массив d и π, чтобы проверить, является ли кратчайший путь от s до t в G уникальным или нет, за O (n log n + m) времени?

Answer 1

Для каждого ребра (u-> v) вдоль кратчайшего пути рассмотрим все другие способы, которыми мы могли бы добраться до v, то есть рассмотрим все остальные вершины x, где есть ребро (x-> v). Если shortest_path(s to u)+|u->v| имеет ту же длину, что и shortest_path(s to x)+|x->v| (где |u->v| означает длину этого ребра), то существует более одного кратчайшего пути от s до t.

Я думаю, что это утверждение if довольно легко следовать, но дайте мне знать, если это не так. Мы также должны проверить, что если кратчайший путь не является уникальным, то эта процедура всегда это выяснит. Интуитивно, я думаю, что это правда, и если это правда, вы, вероятно, можете доказать это, предполагая существование кратчайшего пути, отличного от описанного в π, заявив, что это означает, что второй кратчайший путь отклоняется от π, по крайней мере, в некотором место, и исследуя логические выводы этого.

Answer 2

Это часть HW-5. Пожалуйста, не обманывайте. Я видел ваше другое сообщение об использовании MOSS для назначения DS.