Caminho mais curto para um DAG

Question

Eu tenho um gráfico com um vértice S e T que preciso encontrar o caminho mais curto entre. O gráfico tem muitas propriedades especiais nas quais eu gostaria de capitalizar:

• O gráfico é um DAG (gráfico aciclico direcionado).
• Eu posso criar uma classificação topológica no tempo O (| v |), mais rápido que o O (| V + E |).
• Dentro do tipo topológico, S é o primeiro item da lista e T é o último.

Disseram -me que, uma vez que eu tenho um tipo topológico dos vértices, encontrei o caminho mais curto mais rápido do que meu padrão atual do custo uniforme de Dijkstra, mas não consigo encontrar o algoritmo para ele.

O código pseudo seria muito apreciado.

Edições: Todos os caminhos de S para T têm o mesmo número de arestas. As bordas têm pesos. Estou procurando caminho de custo mais baixo.

Answer 1

Vou contra minha intuição e assumir que isso não é o dever de casa. Você precisa aproveitar as informações que uma ordem topológica fornece. Sempre que você examina o nó n em uma ordem topológica, você tem a garantia de que já atravessou todos os caminhos possíveis para n. Usando isso, fica claro ver que você pode gerar o caminho mais curto com uma varredura linear de uma ordem topológica (pseudocode):

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

Agora você pode procurar um caminho mais curto de S para um destino. Você só precisaria procurar o destino no mapeamento de custos, obter o pai e repetir esse processo até obter um nó cujo pai seja s, então você tem o caminho mais curto.