У меня есть вопрос Учитывая направленный граф G с положительным весом кромки и ориентировочной вершиной x, ваша цель - найти длину кратчайшего пути от одной вершины v до другой вершины w, который проходит через ориентир x.Поиск кратчайшего пути между прохождением через определенную вершину
Необходимо указать алгоритм O (E log V) для проблемы. Я знаю, что сложность алгоритма Дейкстры равна O (ElogV).
Пожалуйста, помогите мне в решении этой проблемы.
Если вы сначала найдете кратчайший путь от v до x, p_1 и от x до w, p_2, используя Алгоритм Дейкстры и возьмите конкатенацию этих путей, p, то это будет самый короткий путь от v до w через x ,
Если бы был более короткий путь, p ', то разделение этого пути на x дало бы путь от v до x, p_1' и один от x до w, p_2 ', где p_1' короче p_1, или p_2 'меньше p_2 (иначе длина (p_1' + p_2 ')> length (p_1 + p_2)), что является противоречием.
EDIT: Это, очевидно, O (E logV), поскольку он просто использует Dijkstra дважды.
Большое спасибо за ваш ответ. – Eng
Всегда рад помочь. –
Можно ли посетить один и тот же край более одного раза? – Daga