Quelle est la signification des bords de poids négatifs dans un graphique?

Je faisais des exercices de programmation dynamique et j'ai trouvé l'algorithme Floyd-Warshall. Apparemment, il trouve les chemins les plus courts de toutes les paires pour un graphique qui peut avoir des bords de poids négatifs, mais pas de cycles négatifs.

Donc, je me demande quelle est la signification réelle des bords de poids négatifs? Une explication simple en anglais serait utile.

Saeed Amiri a déjà donné un excellent exemple dans un commentaire: le poids sur les bords peut représenter n'importe quoi dans le monde réel, par exemple, le montant d'argent à transférer d'un compte à un autre compte. Les montants peuvent être positifs ou négatifs. Par exemple, si vous voulez passer de à b dans votre graphique tout en perdant le moins d'argent possible (chemin le plus court), alors vous pouvez envisager des pondérations négatives. Pour plus d'informations, consultez ce chapitre du livre .$a$$b$

En dehors de cela, il existe de nombreuses autres applications. Les poids négatifs dépendent de ce que vous modélisez. Par exemple, considérez ce graphique

• Chimie: les poids peuvent être utilisés pour représenter la chaleur produite lors d'une réaction chimique. (Modes: composés, arête : si le composé v peut être obtenu ("chimiquement réduit") à partir de u . Dans ce graphique: vous produisez 4 kJ pour convertir s - a et 2 kJ pour convertir a en t . Vous avez besoin de 5 kJ pour récupérer s de t .$e_{uv}$$v$$u$$4$$s-a$$2$$a$$t$$5$$s$$t$

• La vraie vie: Pensez à un chauffeur, qui est payé pour conduire son employeur de à t mais il paie entre a et b (disons voyager entre son domicile et son lieu de travail).$s$$t$$a$$b$

• Jeux: Supposons que vous jouez aux ciseaux de papier de roche pour de l'argent. Nœuds: roche, papier, ciseaux. Bords: toute relation (clique). Poids: pari. Dans ce graphique: (oubliez ), ici, s bat a , a bat t et t bat s , et gagne 4,2, -5 respectivement.$b$$s$$a$$a$$t$$t$$s$

Je ne suis pas un chimiste, mais je pense que cet exemple va vous aider à penser au processeur, à la théorie des réseaux et à tout ce qui s'y rapporte.

Considérons un graphique simulant le comportement d'une molécule dans une réaction chimique, c'est-à-dire quels chemins elle peut prendre pendant la réaction et les poids représentent l'énergie absorbée ou libérée dans la transition, donc si nous voulons que l'énergie sorte de la réaction, nous représentons l'énergie libérée avec + 5 poids et absorbée énergie avec -ve.

Un bord négatif est simplement un bord ayant un poids négatif. Cela pourrait être dans n'importe quel contexte se rapportant au graphique et à quoi se réfèrent ses bords. Par exemple, le bord CD dans le graphique ci-dessus est un bord négatif. Floyd-Warshall fonctionne en minimisant le poids entre chaque paire du graphique, si possible. Ainsi, pour un poids négatif, vous pouvez simplement effectuer le calcul comme vous l'auriez fait pour des bords de poids positifs.

Le problème se pose lorsqu'il y a un cycle négatif. Jetez un œil au graphique ci-dessus. Et posez-vous la question - quel est le chemin le plus court entre A et E? Vous pourriez d'abord vous sentir comme si son ABCE coûte 6 (2 + 1 + 3). Mais en réalité, en y regardant de plus près, vous observeriez un cycle négatif, qui est le BCD. Le poids de BCD est 1 + (- 4) +2 = (-1). En traversant de A à E, je pouvais continuer à parcourir BCD pour réduire mon coût de 1 à chaque fois. Comme, le chemin A (BCD) BCE coûte 5 (2 + (- 1) + 1 + 3). Maintenant, répéter le cycle à l'infini continuerait de réduire le coût de 1 à chaque fois. Je pourrais obtenir un chemin le plus court infini négatif entre A et E.

Le problème est évident pour tout cycle négatif dans un graphique. Par conséquent, chaque fois qu'un cycle négatif est présent, le poids minimum n'est pas défini ou est l'infini négatif, donc Floyd-Warshall ne peut pas fonctionner dans un tel cas.

En outre, vous voudrez peut-être jeter un œil à l' algorithme Bellman-Ford qui détecte si un graphique a un cycle négatif ou non et renvoie le chemin le plus court entre deux nœuds.

Par exemple, imaginons un réseau logistique où le poids w (i, j) d'une arête ij est le coût pour aller du sommet i au sommet j. Si vous avez conclu un accord commercial avec d'autres sociétés pour transporter leurs produits, w (i, j) serait un profit plutôt qu'un coût, vous pouvez donc interpréter ce poids comme un coût négatif.

Congestion du trafic sur une carte:

Un autre exemple concret d'association de poids à un bord pourrait être que les poids représentent les conditions de circulation sur une carte (plus négatifs, plus défavorables) - nous pourrions alors utiliser cette représentation pour calculer les distances optimales.

Nous pouvons vraiment utiliser la métaphore du «poids» pour représenter tout élément de valeur positive / négative entre deux points quelconques dans un graphique