calculer la distance entre les 2 nœuds dans un graphe

J'ai graphe orienté stockées dans le format suivant dans la base de données {STARTNODE, ENDNODE}. Par conséquent, {5,3} signifie qu'il y a une flèche de nœud 5 sur le nœud 3.

Maintenant, j'ai besoin de calculer la distance entre deux aléatoire des nœuds. Quelle est la manière la plus efficace? Par ailleurs, le graphique est a boucles.

Merci beaucoup!

InformationsquelleAutor nababa | 2010-08-30
  1. 9

    Comme vous pouvez le voir ici

    Si vous avez brute bords, vous pouvez utiliser BFS

    Si vous avez des non-négatif bords, vous pouvez utiliser Dijkstra

    Si vous avez négatif ou positif bords-vous le plus l'utilisation Bellman-Ford

    InformationsquelleAutor razpeitia
  3. 3

    Si par la distance, nous entendons le nombre minimum de sauts, vous pouvez vous servir de Guido van Rossum est find_shortest_path fonction:

    def find_shortest_path(graph, start, end, path=[]):
    """
    __source__='https://www.python.org/doc/essays/graphs/'
    __author__='Guido van Rossum'
    """
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

if __name__=='__main__':
    graph = {'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']}
    print(find_shortest_path(graph,'A','D'))
    # ['A', 'B', 'D']
    print(len(find_shortest_path(graph,'A','D')))
    # 3
    InformationsquelleAutor unutbu
  4. 2

    Étant donné que la distance est le nombre de sauts, et est optimale (chemin le plus court.) Vous pouvez garder une trace de nœuds visités et de courant accessible nœuds à l'aide de Python de la liste/set. Commence à partir du premier nœud, puis gardez saut à partir de l'ensemble des nœuds jusqu'à ce que vous atteignez la cible.

    Par exemple, compte tenu de ce graphique:

    calculer la distance entre les 2 nœuds dans un graphe

    [hop 0]
visited: {}
current: {A}

[hop 1]
visited: {A}
current: {B, C, J}

[hop 2]
visited: {A, B, C, J}
current: {D, E, F, G, H}

[hop 3]
visited: {A, B, C, D, E, F, G, H, J}
current: {K} // destination is reachable within 3 hops

    Le point de la visite, la liste des nœuds est d'éviter de visiter les nœuds visités, résultant dans une boucle. Et pour obtenir la distance la plus courte, c'est pas la peine de faire un survol comme il fait toujours la distance de la trajectoire résultante est plus.

    C'est une simple mise en œuvre de En largeur d'abord de recherche. L'efficacité dépend en partie de la façon de vérifier les nœuds visités, et comment faire pour interroger les nœuds adjacents de nœud donné. La Largeur de recherche est toujours la garantie de donner une distance optimale, mais cette mise en œuvre pourrait créer un problème si vous avez beaucoup de nœud, disons milliards de dollars/millions de dollars, dans votre base de données. J'espère que cela donne l'idée.

    InformationsquelleAutor Gant
  5. 0

    Si vous êtes vraiment à la recherche de la manière la plus efficace, la solution est de mettre en œuvre largeur de recherche en C, puis d'appeler la mise en œuvre de l'Python couche. (Bien sûr, cela s'applique uniquement si les bords ne sont pas pondérées; pondéré bords besoin L'algorithme de Dijkstra si les poids sont non-négatives, ou le Bellman-Ford algorithme si le poids peut être négatif).

    D'ailleurs, le igraph bibliothèque met en œuvre tous ces algorithmes en C, de sorte que vous pouvez essayer. Si vous préférez un pur Python-fondé de la solution (ce qui est plus facile à installer que igraph), essayez de le NetworkX paquet.

    InformationsquelleAutor Tamás