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

Question

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

Answer 1

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?

Answer 2

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

Answer 3

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.