Correcless de Bellman-Ford Algorithme, pouvons-nous toujours faire mieux?

Question

J'ai appris que l'algorithme de Bellman-Ford a une durée de fonctionnement de O (| E | * | V |), dans laquelle le E est le nombre de bords et le nombre de sommets.Supposons que le graphique n'a pas de cycles pondérés négatifs.

Ma première question est que comment prouvons-nous que dans (| V | -1) itérations (chaque itération vérifie chaque avantage de E), il met à jour le chemin le plus court vers chaque nœud possible, étant donné un nœud de départ particulier?Est-il possible que nous ayons itétéris (| v | -1) fois mais qui ne se retrouvent toujours pas avec des chemins les plus courts vers chaque nœud?

Assumer l'exactitude de l'algorithme, pouvons-nous réellement faire mieux que cela?Il me semble que tous les bords ne sont pas pondusés négativement dans un graphique particulier.L'algorithme Bellman-Ford semble cher, comme chaque itération passe à tous les bords.

Answer 1

Le chemin le plus long possible de la source à n'importe quel vertice impliquerait au plus tous les autres sommets du graphique. En d'autres termes - vous n'aurez pas de chemin qui traverse la même vertre plus d'une fois, car cela augmenterait nécessairement les poids (cela n'est vrai que grâce au fait qu'il n'y a pas de cycles négatifs).
Sur chaque itération, vous mettriez à jour le poids du chemin le plus court sur la vertice suivante dans ce chemin, jusqu'à After | V | -1 itérations Vos mises à jour devraient atteindre la fin de ce chemin. Après cela, il n'y aura pas de sommets avec des valeurs non serrées, car votre mise à jour a couvert tous les chemins les plus courts jusqu'à cette longueur.

Cette complexité est serrée (au moins pour BF), pensez à une longue ligne de sommets connectés. Choisissez le plus à gauche comme source - votre processus de mise à jour devrait fonctionner de votre côté à l'autre côté une fois la vertice à la fois. Maintenant, vous pourriez dire que vous n'avez pas besoin de vérifier chaque bord de cette façon, alors jetons quelques bords aléatoires avec un très gros poids (N> | V | * max-poids) - ils ne peuvent pas vous aider, mais ils ne peuvent pas vous aider, mais Votre algorithme ne peut pas savoir que, bien sûr, si vous devez passer par le processus de mise à jour des sommets avec ces poids (ils sont encore meilleurs que l'infini initial).