Qual é o significado das arestas de peso negativo em um gráfico?

Eu estava fazendo exercícios de programação dinâmica e encontrei o algoritmo de Floyd-Warshall. Aparentemente, ele encontra os caminhos mais curtos de todos os pares para um gráfico que pode ter arestas de peso negativas, mas sem ciclos negativos.

Então, eu me pergunto qual é o significado real das arestas de peso negativo? Uma explicação simples em inglês seria útil.

Saeed Amiri já deu um excelente exemplo em um comentário: o peso nas bordas pode representar qualquer coisa no mundo real, por exemplo, a quantidade de dinheiro a ser transferida de uma conta para outra. Os valores podem ser positivos ou negativos. Por exemplo, se você quiser ir de para b no gráfico e perder o mínimo de dinheiro possível (caminho mais curto), poderá considerar pesos negativos. Para mais, consulte este capítulo do livro .$a$$b$

Além disso, há muito mais aplicativos. Os pesos negativos dependem de como você o modela. Por exemplo, considere este gráfico

• Química: Os pesos podem ser usados ​​para representar o calor produzido durante uma reação química. (Modos: compostos, borda : se o composto v puder ser obtido ("quimicamente reduzido") de u . Neste gráfico: você produz 4 kJ para converter s - a e 2 kJ para converter a em t . Você precisa de 5 kJ para recuperar s de t .$e_{uv}$$v$$u$$4$$s-a$$2$$a$$t$$5$$s$$t$

• Vida Real: Pense de um motorista, que é pago para conduzir o seu empregador de para t , mas ele paga entre um e $s$$t$$a$$b$ (dizem viajar entre sua casa e seu local de trabalho).

• $b$$s$$a$$a$$t$$t$$s$

Eu não sou um cara de química, mas ainda acho que esse exemplo valerá a pena para ajudá-lo a pensar em processador, teoria de redes e coisas relacionadas.

Considere um gráfico simulando o comportamento de uma molécula em uma reação química, ou seja, quais caminhos ela pode seguir durante a reação e os pesos representam a energia absorvida ou liberada na transição; portanto, se queremos energia fora da reação, representamos a energia liberada com pesos + ve e absorvidos energia com -ve.

Uma aresta negativa é simplesmente uma aresta com um peso negativo. Pode estar em qualquer contexto pertencente ao gráfico e a que bordas se referem. Por exemplo, o CD da aresta no gráfico acima é uma aresta negativa. O Floyd-Warshall funciona minimizando o peso entre cada par do gráfico, se possível. Portanto, para um peso negativo, você pode simplesmente executar o cálculo como faria para as bordas do peso positivo.

O problema surge quando há um ciclo negativo. Dê uma olhada no gráfico acima. E faça a si mesmo a pergunta - qual é o caminho mais curto entre A e E? Você pode inicialmente sentir como se o seu ABCE estivesse custando 6 (2 + 1 + 3). Mas, na verdade, olhando mais profundamente, você observaria um ciclo negativo, que é o BCD. O peso do BCD é 1 + (- 4) +2 = (-1). Ao atravessar de A a E, eu poderia continuar andando de bicicleta dentro do BCD para reduzir meu custo em 1 a cada vez. Assim, o caminho A (BCD) BCE custa 5 (2 + (- 1) + 1 + 3). Agora, repetir o ciclo infinitos vezes continuaria reduzindo o custo em 1 a cada vez. Eu poderia conseguir um caminho mais curto infinito negativo entre A e E.

O problema é evidente para qualquer ciclo negativo em um gráfico. Portanto, sempre que um ciclo negativo está presente, o peso mínimo não é definido ou é infinito negativo, portanto, Floyd-Warshall não pode funcionar nesse caso.

Além disso, você pode dar uma olhada no algoritmo de Bellman-Ford, que detecta se um gráfico tem ciclo negativo ou não e, de outra forma, retorna o caminho mais curto entre dois nós.

Por exemplo, imagine uma rede logística em que o peso w (i, j) de uma aresta ij seja o custo para ir do vértice i ao vértice j. Se você fez um acordo comercial com outras empresas para transportar seus produtos, w (i, j) seria um lucro em vez de um custo, para que você possa interpretar esse peso como um custo negativo.

Congestionamento de tráfego em um mapa:

Um outro exemplo do mundo real de associação de pesos a uma borda pode ser o peso que representa as condições de tráfego em um mapa (mais negativo, mais desfavorável) - poderíamos então usar essa representação para calcular distâncias ideais.

Podemos realmente usar a metáfora "peso" para representar qualquer coisa de valor positivo / negativo entre quaisquer dois pontos em um gráfico