Reconstruction du chemin Floyd-Warshall

Question

Vous trouverez ci-dessous l'implémentation de l'algorithme Floyd-Warshall, qui trouve les chemins les plus courts de toutes les paires pour un graphe pondéré donné.

La fonction floyd_warshallprend un graphique comme entrée, qui est représenté par une liste d'arêtes sous la forme de [ source , destination , poids ]

La path_reconstructionfonction génère les chemins les plus courts de chaque sommet connecté à chaque autre sommet.

Veuillez fournir des suggestions d'améliorations de quelque nature que ce soit.

import sys

INF = sys.maxsize

def floyd_warshall(graph):
    source_vertices = [column[0] for column in graph]
    destination_vertices = [column[1] for column in graph]
    vertices = list(set(source_vertices) | set(destination_vertices))

    distance = [[INF] * len(vertices) for i in range(len(vertices))]
    next_vertices  = [[0]   * len(vertices) for i in range(len(vertices))]

    for i in range(len(vertices)):
        distance[i][i] = 0
    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight
        next_vertices[source-1][destination-1] = destination-1

    for k in range(len(vertices)):
        for i in range(len(vertices)):
            for j in range(len(vertices)):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_vertices[i][j]  = next_vertices[i][k]

    path_reconstruction(distance, next_vertices)

def path_reconstruction(dist, nxt):
    print("Edge \t\t Distance \t Shortest Path")
    for i in range(len(dist)):
        for j in range(len(dist)):
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(nxt[path[-1]][j])
                print("(%d, %d) \t\t %2d \t\t %s"
                      % (i + 1, j + 1, dist[i][j], ' - '.join(str(p + 1) for p in path)))
    print()

def main():
    edge_list1 = [
        [1, 3, -2],
        [2, 1, 4],
        [2, 3, 3],
        [3, 4, 2],
        [4, 2, -1]
    ]
    edge_list2 = [
        [1, 2, 10],
        [1, 3, 20],
        [1, 4, 30],
        [2, 6, 7],
        [3, 6, 5],
        [4, 5, 10],
        [5, 1, 2],
        [5, 6, 4],
        [6, 2, 5],
        [6, 3, 7],
        [6, 5, 6]
    ]

    floyd_warshall(edge_list1)
    floyd_warshall(edge_list2)

if __name__ == '__main__':
    main()

Answer 1

FMc a fait quelques excellents points. J'essaierai de ne pas les répéter.

Sommets

Vous déterminez la liste des sommets en utilisant:

    source_vertices = [column[0] for column in graph]
    destination_vertices = [column[1] for column in graph]
    vertices = list(set(source_vertices) | set(destination_vertices))

puis utilisez à plusieurs reprises tout au len(vertices)long de votre code.

FMc suggère d'utiliser:

    vertices = set(col[i] for col in graph for i in (0, 1))
    n = len(vertices)

Les deux implémentations utilisent des ensembles pour former une couverture de tous les sommets. Mais cela n'a vraiment aucun sens. Vous utilisez range(len(vertices))pour déterminer les indices. Et si les graphiques utilisaient les sommets 1, 2, 4 et 5? Vos jeux seraient {1, 2, 4, 5}, la longueur de l'ensemble est 4, et range(4)produit les indices 0, 1, 2et 3. Mais vous exécutez:

    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight

vous trouverez sourceou destinationest 5, calculez soustrayez 1, pour obtenir l'indice 4, et trouvez que vous êtes tombé de la fin de la matrice!

De toute évidence, il existe une exigence selon laquelle tous les indices de 1à Ndoivent être utilisés, sans aucune lacune autorisée. Mais alors, vous n'avez pas besoin d'un ensemble. Il vous suffit de trouver l'index maximum.

    n = max(edge[col] for edge in graph for col in (0, 1))

L'indexation est lente

Dans ce code, pour 100 sommets, combien de fois est distance[i]évalué? Et pourquoi pas distance[k]?

    for k in range(len(vertices)):
        for i in range(len(vertices)):
            for j in range(len(vertices)):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_vertices[i][j]  = next_vertices[i][k]

distance[i]est recherché quelque part entre 2000000 et 4000000 fois? Cela semble excessif, peut-être? distance[k]est recherché entre 1000000 et 2000000 fois. Un tout petit peu moins, mais encore pas mal.

Une fois que vous êtes entré, la première forboucle kest une constante pour cette itération. Vous pouvez rechercher distance[k]une fois. De même, une fois que vous êtes entré dans la deuxième forboucle, il iy a une constante pour cette itération. Vous pouvez rechercher distance[i]une fois.

    for k in range(len(vertices)):
        distance_k = distance[k]
        for i in range(len(vertices)):
            distance_i = distance[i]
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

Maintenant, recherchaient la distance [k] seulement 100 fois, et la distance [i] seulement 10000 fois. Ce sera une amélioration de la vitesse.

Nous pouvons mieux faire les boucles for: obtenir les indices et rechercher les valeurs ensemble, en utilisant enumerateet en boucle sur les lignes de la distancematrice:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

Encore une fois, distance_i[k]ne change pas dans la boucle interne, nous pouvons donc le rechercher une fois dans la boucle du milieu:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j in range(len(vertices)):
                dist_ik_kj = dist_ik + distance_k[j]
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

Enfin, nous pouvons itérer sur la distance_kligne de la matrice, pour éviter les frais généraux de recherche d'addition:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j, dist_kj in enumerate(distance_k):
                dist_ik_kj = dist_ik + dist_kj
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

Les deux next_vertices[i]et next_vertices[i][k]sont constants dans la boucle interne; nous pourrions les rechercher une fois dans la boucle du milieu, pour des économies supplémentaires. Vous pouvez même zip distanceet next_verticesensemble dans la for i, ...déclaration et rechercher les deux distance_iet next_vertices_isimultanément. Mais peut-être que cela devient un peu trop avancé.

Mémoire

Les listes Python sont des porcs de mémoire. Cela n'a pas d'importance si vos graphiques n'ont pas plus de quelques centaines de sommets. Mais si vous voulez prendre en charge des graphes plus grands (des milliers de sommets? Des centaines de milliers de sommets?), Vous voudrez utiliser des structures efficaces en mémoire.

Vous pouvez utiliser numpypour créer votre NxN distanceet vos next_verticesmatrices. Mais si vous ne l'avez pas numpyinstallé, nous n'avons pas besoin d'utiliser ce marteau. Python est livré avec des arrayobjets plus efficaces en mémoire , qui ne peuvent stocker que des informations scalaires (entiers, flottants, caractères) au lieu des listes hétérogènes Jack-of-All-Trade de listes.

next_verticescontenir des valeurs de sommet entières. À la place de:

next_vertices  = [[0]   * len(vertices) for i in range(len(vertices))]

considérer:

zeros = [0] * len(vertices)
next_vertices = [array.array('I', zeros) for _ in range(len(vertices))]

Le reste du code n'aurait pas besoin de changer. Vous accédez toujours aux données comme next_vertices[i][j].

Cela crée un nombre listd' arrayentiers, où le tableau ne prend que 2 octets par valeur, au lieu de 8 octets par élément, plus l'exigence de stockage de chaque entier (environ 28 octets chacun).

Vous pouvez faire quelque chose de similaire pour la distancematrice. Mais maintenant, nous devons savoir: les poids sont-ils toujours des valeurs entières ou sont-ils à virgule flottante? Vous voudrez peut-être utiliser le 'd'code de type, si les pondérations peuvent être fractionnaires. Voir le tableau pour plus de détails.

Answer 2

Votre programme fournit un bon exemple pour voir comment on peut augmenter la lisibilité du code grâce à certaines techniques courantes: (1) des variables de commodité pour éviter les répétitions verbeuses; (2) code organisé en petits "paragraphes" ou blocs commentés; et (3) l'utilisation de noms de variables plus courts pour alléger le poids visuel du code, améliorant ainsi la facilité de lecture et de balayage visuel. Notez que les noms courts doivent être utilisés judicieusement: parce qu'ils peuvent être cryptiques, les vars courts tirent généralement leur signification soit d'une convention systématiquement utilisée dans le programme, soit d'autres indices contextuels (par exemple, de fonctions ou de collections proches ayant des noms plus explicites et de bien - commentaires placés). Voici une version fortement modifiée defloyd_warshall()le long de ces lignes. Parce que je suis paresseux, je suppose que vous avez correctement implémenté Floyd-Warshall.

def floyd_warshall(graph):
    # Collect all vertices.
    vertices = set(
        col[i]
        for col in graph
        for i in (0, 1)
    )
    n = len(vertices)
    rng = range(n)

    # Initialize the distance and next-vertex matrix.
    dists = [
        [0 if i == j else INF for j in rng]
        for i in rng
    ]
    next_vertices = [
        [0 for j in rng]
        for i in rng
    ]

    # Populate the matrixes.
    for src, dst, weight in graph:
        i = src - 1
        j = dst - 1
        dists[i][j] = weight
        next_vertices[i][j] = j

    # Do that Floyd-Warshall thing.
    for k in rng:
        for i in rng:
            for j in rng:
                ikj = dists[i][k] + dists[k][j]
                if dists[i][j] > ikj:
                    dists[i][j] = ikj
                    next_vertices[i][j]  = next_vertices[i][k]

    return path_reconstruction(dists, next_vertices)

Un problème plus important est que votre floyd_warshall()fonction ne doit pas appeler une fonction qui s'imprime. Il devrait plutôt renvoyer une sorte de données significatives. Cette approche rend votre fonction plus facilement testable. Par exemple, path_reconstruction()pourrait renvoyer une liste de dictés déclaratifs.

def path_reconstruction(dists, next_vertices):
    # Same ideas here: return data, don't print; use convenience
    # vars where they help with readability.
    rng = range(len(dists))
    paths = []
    for i in rng:
        for j in rng:
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(next_vertices[path[-1]][j])
                paths.append(dict(
                    i = i,
                    j = j,
                    dist = dists[i][j],
                    path = path,
                ))
    return paths

Ensuite, faites votre impression en dehors du code algorithmique.

def main():
    edge_lists = [
        [
            [1, 3, -2],
            [2, 1, 4],
            [2, 3, 3],
            [3, 4, 2],
            [4, 2, -1],
        ],
        [
            [1, 2, 10],
            [1, 3, 20],
            [1, 4, 30],
            [2, 6, 7],
            [3, 6, 5],
            [4, 5, 10],
            [5, 1, 2],
            [5, 6, 4],
            [6, 2, 5],
            [6, 3, 7],
            [6, 5, 6],
        ],
    ]
    for el in edge_lists:
        paths = floyd_warshall(el)
        for p in paths:
            print(p)