Modifié chemin le plus court en utilisant l'algorithme de Dijkstra ou de Bellman-Ford

Question

Comment peut-on utiliser de Dijkstra ou l'algorithme de Bellman-Ford pour trouver plus court chemin dans un graphe dont certains des bords sont touchés si nous sommets spécifiques. De telle sorte que, la longueur de bord affectée sera plus ou moins de la longueur d'origine.

Answer 1

Si je comprends bien, vous voulez changer le coût d'un bord dans un graphique en fonction des noeuds qui sont visités dans votre chemin en cours. Un exemple des commentaires est:

"bord AB a une longueur 3, mais si vous visitez également le nœud C, la longueur de AB sera 5"

Maintenant, il ne semble pas être un moyen pour quelque chose comme l'algorithme de Djikstra à utiliser comme il y a une étape gourmande dans cet algorithme qui prend le nœud « meilleur » à chaque étape. L'idée que le nœud « meilleur » à ce moment-là peut changer à une date ultérieure (en raison d'une règle telle que ci-dessus) viole le concept de l'approche baveuse, ce qui suppose que nous visitions efficacement les nœuds afin de mieux au pire coût. Je ne suis pas certain si cela est NP dur comme suggéré, mais il ne peut certainement pas utiliser une sorte Dijikstra d'approche dès le début. +1 pour le problème cependant.