Encontre o caminho mais longo em um gráfico cíclico direcionado de uma fonte S para um destino f. Suponha que não exista ciclos de peso positivo
-
27-09-2019 - |
Pergunta
Eu tenho que encontrar o caminho mais longo em um gráfico cíclico direcionado de uma fonte s para um destino f. Suponha que não exista ciclos de peso positivo, embora não existam ciclos de peso positivo, existem ciclos de 0 ou pesos negativos. Alguém pode sugerir um algoritmo para encontrar o caminho mais longo neste caso. Por favor, cite a fonte, se possível.
obrigado
Solução
Não tenho certeza se isso funcionará (preciso verificar), mas ... você pode fazer algo semelhante a:
Deixar min = min weight on the graph
.
max = max weight on the graph
.
Defina novos pesos para todas as arestas = wNew(e) = max - (wOld(e)-min)
.
Agora existem wights negativos e os pesos estão em ordem inversa (ou seja, se w(e1)
era maior que w(e2)
agora é menor).
E se agora procurarmos o caminho mais curto?
Outras dicas
Apenas negue os pesos da borda e execute um algoritmo de caminho mais curto (por exemplo, Bellman-Ford).
Os ciclos de peso zero podem ser um problema. Você precisará quebrar os laços em seus caminhos escolhendo o mais curto (de comprimento, não com peso). Uma maneira de fazer isso é fazer com que seus pesos sejam um par (-(peso original), 1), adicione-os emparelhados e faça pedidos lexicográficos.
Veja também Caminho mais longo entre dois vértices
Se você adquiriu um DCG, poderá fazer um loop para sempre antes de chegar ao seu alvo, esse seria o "caminho mais longo". Nesse caso, a questão é incompleta e o algoritmo provavelmente parece diferente, dependendo dos detalhes.
Isso soa como lição de casa.