Кратчайший путь для дага

У меня есть граф с вершинами s и t, между которыми мне нужно найти кратчайший путь. У графика есть много специальных свойств, на которых я хотел бы извлечь выгоду:

  • Граф представляет собой DAG (ориентированный ациклический граф).
  • Я могу создать топологическую сортировку за O (| V |) время, быстрее, чем при традиционном O (| V + E |).
  • В топологической сортировке s - это первый элемент в списке, а t - последний.

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

Псевдокод был бы очень признателен.

РЕДАКТИРОВАНИЕ: все пути от s до t имеют одинаковое количество ребер. Края имеют веса. Я ищу самый дешевый путь.


graph directed-acyclic-graphs algorithm shortest-path
person user108088    schedule 27.09.2009    source источник
comment
Чтобы уточнить, вы пытаетесь найти наименьшее расстояние или наименьшее количество ребер? Края разной длины?   -  person Joey Adams    schedule 27.09.2009
comment
Кроме того, можете ли вы переходить по резервным ссылкам по кратчайшему пути или только вниз?   -  person Joey Adams    schedule 27.09.2009

Ответы (1)


arrow_upward
21
arrow_downward

Я собираюсь пойти против своей интуиции и предположить, что это не домашнее задание. Вы должны воспользоваться информацией, которую дает вам топологический порядок. Всякий раз, когда вы исследуете узел n в топологическом порядке, у вас есть гарантия, что вы уже прошли все возможные пути к n. Используя это, ясно, что вы можете сгенерировать кратчайший путь с помощью одного линейного сканирования топологического упорядочения (псевдокода):

Graph g
Source s
top_sorted_list = top_sort(g)

cost = {} // A mapping between a node, the cost of its shortest path, and 
          //its parent in the shortest path

for each vertex v in top_sorted_list:
  cost[vertex].cost = inf
  cost[vertex].parent = None

cost[s] = 0

for each vertex v in top_sorted_list:
   for each edge e in adjacensies of v:
      if cost[e.dest].cost > cost[v].cost + e.weight:
        cost[e.dest].cost =  cost[v].cost + e.weight
        e.dest.parent = v

Теперь вы можете найти любой кратчайший путь от s до пункта назначения. Вам просто нужно будет найти пункт назначения в сопоставлении затрат, получить его родительский элемент и повторять этот процесс, пока вы не получите узел, родительский элемент которого равен s, тогда у вас будет кратчайший путь.

person Falaina    schedule 27.09.2009
comment
Спасибо за ответ, но я не могу понять, что означает e.dest? Может кто-нибудь прояснить это? - person ; 24.05.2010
comment
Ребра здесь на самом деле являются направленными дугами. e.dest - это узел, на который указывает край. - person user108088; 28.05.2010
comment
dest означает пункт назначения. - person Nixuz; 08.11.2010
comment
Я думаю, у вас может быть небольшая проблема с вашим псевдокодом, расслабляющим узел e.dest. Должен ли он быть {if cost [e.dest] .cost ›cost [v] .cost + e.weight;}? - person Gin; 30.03.2011