algorithme pour trouver le nombre de chemins distincts dans un graphe orienté

Possible en double:
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices algorithme pour trouver le nombre de chemins distincts dans un graphe orienté

J'ai un graphe orienté, quel algorithme puis-je utiliser pour trouver le nombre de distincts chemins acycliques entre 2 sommets particuliers, et compte le nombre maximum de fois qu'un chemin est utilisé dans ces chemins distincts? Deux chemins sont distincts s'ils visitent un nombre différent de sommets ou s'ils visitent des sommets dans un ordre différent.

Source

2009-10-29 Pranav

À mon humble avis Il ne doit pas nécessairement s'agir d'un doublon. Il y a une différence entre connaître le nombre de valeurs (entier) et connaître toutes les valeurs (un ensemble de listes de nœuds). Pour mon but, même une estimation raisonnable du nombre (limite supérieure) est OK donc pour moi ce n'est pas un doublon. – danatel

[Algorithme de graphes pour trouver toutes les connexions entre deux sommets arbitraires] (http://stackoverflow.com/q/58306) n'est pas du tout un doublon: l'énumération et le comptage sont des problèmes différents, et un graphe orienté est une bête différente d'un graphe non orienté. En ce qui concerne la complexité du comptage des chemins simples, voir [Comment comptez-vous le nombre de chemins simples entre deux nœuds dans un graphe orienté?] (Http://cs.stackexchange.com/q/423) sur [cs.se]. – Gilles

Je suis d'accord avec Danatel - pour les grands graphiques, il n'est pas souhaitable de compter une énumération de tous les chemins possibles. –

Si vous suivez un algorithme de Dijkstra légèrement modifié, vous pouvez avoir une solution pour toutes les paires.

Explication: Les chemins de u à v est la somme des éléments suivants:

chemins u-v qui ne passe pas par w
chemins qui passent par w = nombre de chemins de u à wfois nombre de voies de w à v

Initialiser la matrice avec des zéros, sauf s'il y a un front de i à j (qui est 1). Ensuite, l'algorithme suivant vous donnera le résultat (tout paire chemin-comptage)

for i = 1 to n: 
    for j = 1 to n: 
     for k = 1 to n: 
      paths[i][i] += paths[i][k] * paths[k][j]

Inutile de dire que: O(n^3)

Désireuse de lire une seule solution de paire. :)

Source

2009-10-29 09:08:38 ThisIsMeMoony

Cette solution ne traite pas correctement l'exigence selon laquelle les chemins ne doivent pas avoir de cycles. – hugomg

Ceci est un Bellman-Ford modifié, pas un Dijkstra modifié (d'où le problème du cycle). –

algorithme pour trouver le nombre de chemins distincts dans un graphe orienté

Répondre

Questions connexes