chemins les plus courts pas le chemin dans le graphique

Je me demandais s'il y a un algorithme qui trouverait les chemins les plus courts dans le graphique. Disons que j'ai un graphe où il y a des couples de chemin d'un sommet à l'autre. Deux ou plusieurs de ces chemins ont le même coût. Comment puis-je marquer, trouver etc. tous les chemins les plus courts entre ces sommets? Autant que je sache, les algorithmes de Dijkstra ou de Bellman-Ford trouveront le chemin le plus court, mais ils n'en "choisissent" qu'un seul.chemins les plus courts pas le chemin dans le graphique

Source

2010-08-09 Berial

Trouvez le chemin le plus court. S'il y a d'autres chemins de la même distance, trouvez-les aussi? –

L'algorithme de Dijkstra vous donne le coût de tous les noeuds intermédiaires possibles, et le coût du plus court chemin vers le puits. Vous pouvez obtenir tous les chemins de la source à l'enfoncement en effectuant une première recherche en profondeur de l'évier à la source (en remontant), où vous traversez un bord (en arrière) uniquement si le coût de ce bord est égal à la différence le chemin le plus court entre la source et les deux nœuds. Bien sûr, vous obtenez les chemins dans l'ordre inverse, mais les inverser est facile.

Source

2010-08-09 16:05:51 deinst

Pourriez-vous me donner un exemple? Je ne pense pas avoir bien compris. Je devrais commencer à partir du sommet du puits et faire DFS, il est clair, mais je ne comprends pas la condition de traverser un bord – Berial

Ok Commencez par le sommet du puits, disons que votre algorithme de chemin le plus court indique qu'il est à 20 . Dites qu'il y a trois sommets qui mènent au lavabo, appelez-les a, b, c, appelez le lavabo x. Dire que a est à distance 18 de la source, et le bord ax a le poids 2, b est la distance 17 de la source et bx a le poids 4, et c est 19 de la source et cx a le poids 1. Cela signifie qu'il y a le plus court chemins de la source à l'évier qui se terminent par une hache et avec cx. Utilisez cette procédure pour lister tous les chemins se terminant par ax, puis tous les chemins se terminant par cx. – deinst

Ok je pense que j'ai réussi à écrire ceci :) Je dois tester mon programme et je levais Vous savez si tout est OK – Berial

Jetez un oeil à Floyd-Warshall.

Dans l'informatique, l'algorithme Floyd-Warshall (parfois connu sous le nom WFI algorithme ou algorithme Roy-Floyd) est un algorithme d'analyse graphique pour trouver chemins les plus courts dans un graphe pondéré (avec bord positif ou négatif poids). Une seule exécution de l'algorithme trouvera les longueurs (poids totalisés) des chemins les plus courts entre toutes les paires de sommets, bien que ne renvoie pas les détails des chemins eux-mêmes. L'algorithme est un exemple de programmation dynamique .

Source

2010-08-09 17:41:56

Comment cela aide-t-il? La question concerne tous les chemins les plus courts entre deux sommets donnés. Il n'y a qu'une seule paire. –

@Moron - Oh, mon erreur. J'avais l'impression que Berial disait que ces algorithmes ne trouvaient que le plus court entre deux nœuds, plutôt que tous les chemins également courts entre deux nœuds spécifiques. Floyd-Warshall trouvera tous les chemins les plus courts dans un graphique, plutôt que tous les chemins les plus courts entre deux sommets. –

chemins les plus courts pas le chemin dans le graphique

Répondre

Questions connexes