Décidez si tous les chemins les plus courts de s à t contiennent le bord e

Question

Soit G = (V; E) un graphe orienté dont les arêtes ont toutes des poids non négatifs. Soit s, t deux vertices dans V, et soit e une arête dans E. Décrire un algorithme qui décide si tous les chemins les plus courts de s à t contiennent le bord e. Eh bien, voici comment vous pouvez réaliser la complexité temporelle de Dijsktra: Exécutez simplement Dijkstra à partir de s et calculez delta (s, t) (le poids du chemin le plus court de s à t). Supprimez le bord e et réexécutez Djikstra à partir de s dans le nouveau graphique. Si delta (s, t) dans le nouveau graphique a augmenté, cela signifie que tous les chemins les plus courts de s à t contiennent le bord e, sinon ce n'est pas vrai.

Je me demandais s'il y avait un algorithme plus efficace pour résoudre ce problème. Pensez-vous qu'il est possible de battre la complexité du temps de Dijkstra?

Merci d'avance

Answer 1

Votre approche me semble correcte. Vous calculez simplement le chemin le plus court avec et sans la possibilité de prendre bord e. Cela vous donne 2 recherches Dijkstra.

Il y a place à l'amélioration si vous allez à A *, recherche bidirectionnelle ou récupérer votre arbre de recherche Dijkstra:

• A * accélérerait votre Dijkstra-requête, mais il pourrait ne pas être possible pour votre graphique en vous devez être en mesure de définir une bonne limite sur votre distance restante.
• La recherche bidirectionnelle peut être effectuée avec les deux recherches se rencontrant autour du bord. Vous pouvez alors examiner tous les chemins avec et sans le bord avec seulement 1 requête bidirectionnelle rapide + un travail supplémentaire pour les deux cas au lieu d'avoir 2 Dijkstra complets qui sont très similaires
• vous pouvez rechercher une fois sans bord et maintenir votre arbre de recherche. Ensuite, vous ajoutez e et mettez à jour l'arbre du plus court chemin à partir du point de départ de e. Si l'étiquette du point final> l'étiquette du point de départ + la longueur e, le point final peut être atteint plus rapidement en utilisant e. Effectuez une recherche récursive des voisins de votre point final et ne mettez à jour les distances que si elles peuvent être atteintes plus rapidement qu'auparavant. Devrait vous épargner du travail.