meilleur algorithme pour trouver la distance pour toutes les paires où le poids des bords est 1
comme le titre le dit, j'essaie d'implémenter un algorithme qui découvre les distances entre toutes les paires de noeuds dans un graphe donné. Mais il y a plus: (des choses qui pourraient vous aider)
- le graphique n'est pas pondéré. ce qui signifie que tous les bords peuvent être considérés comme ayant un poids de 1.
|E| <= 4*|V|- Le graphique est assez grand (au plus ~144 profondeur)
- Le graphe est orienté
- Il pourrait y avoir des cycles
- je suis en train d'écrire mon code en python (s'il vous plaît si vous faites référence à des algorithmes, le code serait sympa aussi :))
je sais algorithme de Johnson, Floyd-Warshal et Dijkstra pour toutes les paires. Mais ces algorithmes sont bons quand le graphe a des poids.
je me demandais s'il y avait un meilleur algorithme pour mon cas, parce que ces algorithmes sont destinés à des graphiques pondérés.
Merci!
10 réponses
il y a place à amélioration parce que dans les graphiques non pondérés, vous obtenez un attribut supplémentaire qui ne tient pas pour les graphiques pondérés, à savoir:
pour tout bord reliant directement A à C, vous savez avec certitude qu'il n'y a pas de chemin plus court via un troisième noeud B.
en gardant cela à l'Esprit, vous devriez être en mesure de simplifier L'algorithme de Dijkstra: comme vous le savez peut-être, il fonctionne avec trois ensembles de noeuds:
- ceux dont le régime définitif le plus court chemin est connu,
- ceux dont une distance préliminaire a été calculée et
- ceux qui n'ont pas encore été explorées.
en suivant un bord eA (1.)C (3.), l'original de Dijkstra serait déplacer le nœud C à partir de (3. à 2.). Puisque l'attribut ci-dessus tient dans tous vos graphiques, vous pouvez cependant l'ajouter directement à l'ensemble (1.), qui est plus efficace.
Voici l'observation essentielle: La procédure décrite ci-dessus est essentiellement un BFS (width first search), c'est-à-dire que vous pouvez trouver la distance à partir d'un noeud fixe v pour n'importe quel autre nœud O(|V| + |E|).
vous n'avez pas mentionné dans votre question originale que le graphique était essentiellement une grille avec quelques trous. C'est encore plus forte exigence, et je suis sûr que vous pouvez exploiter. Faire une recherche rapide pour "grille graphique chemin le plus court", les rendements ce document quelles promesses O(sqrt(n)) dans le meilleur des cas. Comme l' problème que vous précisez est assez bien structuré, je suis presque sûr qu'il ya plusieurs autres documents que vous pourriez vouloir examiner.
effectuer une recherche étendue-d'abord à partir de chaque noeud. Durée totale: O (|V || E|) = O (|V/2), ce qui est optimal.
Je ne sais pas comment vous pouvez mesurer la distance si tous les bords ne sont pas pondérés, mais vous voulez regarder l'algorithme Blossom V D'Edmond. Vous voulez regarder http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs. Voici quelque chose de similaire: http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html.
Qu'en est-il de L'algorithme de Warshall, avec l'implémentation très simple suivante:
def warshall(graph):
n = graph.numNodes+1
W = [ [graph.w(i,j) for j in graph.V()] for i in graph.V() ]
for k in range(1,n):
for i in range(1,n):
for j in range(1,n):
W[i][j] = min( W[i][j] , W[i][k]+W[k][j] )
return W
où
V()rendement de tous les sommets du graphew(i,j)donne le poids de bord (I, j) - dans votre cas tout 1 ou 0numNodesdonnez le nombre de noeuds du graphe.
la complexité est, cependant, O (N^3)
je vous renvoie à L'article suivant: "Sub-cubic Cost Algorithms for the All Pairs Shortest Path Problem" de Tadao Takaoka. Il existe un algorithme séquentiel avec une complexité sub-cubique pour les graphiques avec un poids unitaire (en fait le poids de Bord max = O(N ^ 0.624)).
je suppose que le graphe est dynamique; sinon, il n'y a aucune raison de ne pas utiliser Floyd-Warshall pour précalculer les distances toutes paires sur un graphe aussi petit ;)
supposons que vous ayez une grille de points (x, y) avec 0 <= x <= n, 0 <= y <= N. En enlevant un bord E: (i, j) < - > (i+1, j), vous divisez la rangée j en ensembles A = {(0, j), ..., (I, j)}, B = {(i+1, j),..., (n, j) } tels que les points a EN A, b en B sont forcé pour contourner E-donc vous n'avez besoin que de recalculer la distance pour toutes les paires (a, b) en (a, b).
peut-être que vous pouvez précalculer Floyd-Warshall, alors, et utiliser quelque chose comme ça pour réduire la recomputation à O(N^2) (ou donc) par modification de graphe...
je vous suggère de donner networkx un essai, il semblait aller bien avec 1000 nœuds.
le lien suivant contient les algorithmes du chemin le plus court pour les graphiques non pondérés:
http://networkx.lanl.gov/reference/algorithms.shortest_paths.html
Voici un exemple avec 10 nœuds:
from random import random
import networkx as nx
G=nx.DiGraph()
N=10
#make a random graph
for i in range(N):
for j in range(i):
if 4*random()<1:
G.add_edge(i,j)
print G.adj
print nx.all_pairs_shortest_path(G)
print nx.all_pairs_shortest_path_length(G)
#output:
#Graph ADJ={0: {}, 1: {}, 2: {}, 3: {0: {}, 2: {}}, 4: {}, 5: {0: {}, 3: {}, 4: {}}, 6: {0: {}, 1: {}, 4: {}}, 7: {2: {}, 4: {}, 6: {}}, 8: {1: {}}, 9: {2: {}, 5: {}}}
#PAIRS={0: {0: [0]}, 1: {1: [1]}, 2: {2: [2]}, 3: {0: [3, 0], 2: [3, 2], 3: [3]}, 4: {4: [4]}, 5: {0: [5, 0], 2: [5, 3, 2], 3: [5, 3], 4: [5, 4], 5: [5]}, 6: {0: [6, 0], 1: [6, 1], 4: [6, 4], 6: [6]}, 7: {0: [7, 6, 0], 1: [7, 6, 1], 2: [7, 2], 4: [7, 4], 6: [7, 6], 7: [7]}, 8: {8: [8], 1: [8, 1]}, 9: {0: [9, 5, 0], 2: [9, 2], 3: [9, 5, 3], 4: [9, 5, 4], 5: [9, 5], 9: [9]}}
#LENGTHS={0: {0: 0}, 1: {1: 0}, 2: {2: 0}, 3: {0: 1, 2: 1, 3: 0}, 4: {4: 0}, 5: {0: 1, 2: 2, 3: 1, 4: 1, 5: 0}, 6: {0: 1, 1: 1, 4: 1, 6: 0}, 7: {0: 2, 1: 2, 2: 1, 4: 1, 6: 1, 7: 0}, 8: {8: 0, 1: 1}, 9: {0: 2, 2: 1, 3: 2, 4: 2, 5: 1, 9: 0}}
dans le projet de graphique Python:
http://code.google.com/p/python-graph/
vous pouvez trouver mon implémentation de l'algorithme A* avec un support pour l'heuristique-hinting. Ceci est particulièrement approprié pour l'évitement d'obstacles en 2 dimensions car l'algorithme de hinting n'a pas besoin d'être autre chose que le théorème de pythogras.
je pense que ça ferait tout ce que tu veux. Si vous n'aimez pas les abstractions graphiques utilisées par ce projet, vous pouvez réutiliser algorithme. Il est écrit dans un très générique.
Après la prise d'un mouvement rapide à travers la Conception d'un Algorithme Manuel
L'algorithme principal pour trouver le chemin le plus court est L'algorithme de Djikstra ... votre graphique est-il pondéré ou non pondéré? si votre graphique n'est pas pondéré, un simple largeur-la première recherche à partir du sommet source trouvera le chemin le plus court vers tous les autres sommets en temps linéaire... Il cite les autres cas, vous pourriez être intéressés (par exemple, si l'entrée est un ensemble de figures géométriques obstacles? Avez-vous besoin du chemin le plus court entre toutes les paires de points?) mais dans ces cas, il conclut aussi la même chose que vous: l'algorithme de Djikstra ou l'algorithme de Floyd-Warshall. selon votre utilisation, vous pouvez également vouloir pour regarder dans Fermetures Transitoires qui traitent de la possibilité d'accès, et utilisent des algorithmes similaires.
def from_vertex(v, E):
active = [v]
step = 0
result = {v:0}
while active:
step += 1
new_active = []
for x in active:
for nh in E[x]:
if nh not in result:
new_active.append(nh)
result[nh] = step + 1
active = new_active
return result
fondamentalement, vous faites un remplissage d'inondation de chaque vertex et vous obtenez comme résultat la distance minimale de tout autre vertex accessible à partir de celui-ci.