2

Tengo el siguiente código que calcula la distancia más corta entre dos nodos que yo le indique, pero quisiera que me saliera una lista con la distancia más corta entre cada uno de los nodos, ejemplo:

Distancia entre nodo A y nodo B=1
Distancia entre nodo A y nodo C=1
Distancia entre nodo A y nodo D=1
.
.
.
Distancia entre nodo F y nodo G = 0

El código es el siguiente:

class Grafo():
    grafo = nx.DiGraph()
    vertices = ['A', 'B', 'C', 'D', 'E','F', 'G']
    conexiones = [('A', 'B'), ('A', 'C'),('C','D'), ('E','F'), ('F','B'), ('B', 'G'),('G', 'D')]
    def inicializar2(self):
        self.grafo.add_nodes_from(self.vertices)
        self.grafo.add_edges_from(self.conexiones)

        distancia_corta  = nx.dijkstra_path_length(self.grafo, 'A', 'B') '''En esta parte en vez de pasarle A y B quisiera hacer un iterador que recorra cada nodo'''
        iterara en cada uno de los nodos
        print("La distancia entre A y B es: ", distancia_corta)
2
  • 2
    ¿Por que has eliminado el código de tu pregunta? así como está ahora debiera cerrarse, lo cual sería una pena por la buena respuesta que ya obtuviste. el 4 jun. 2020 a las 15:12
  • 1
    Por favor, no vandalizes tu propia pregunta, a menos que tengas un motivo concreto para hacerlo
    – gbianchi
    el 4 jun. 2020 a las 15:21

1 respuesta 1

3

Debes usar en principio all-pairs-dijkstra-path-length. Retorna un generador que en cada iteración genera una tupla de la forma:

(NodoA, {NodoB: distancia entre NodoA y NodoB, NodoC: distancia entre NodoA y NodoC, ...})

es decir, en tu caso algo como:

('A', {'A': 0, 'B': 1, 'C': 1, 'G': 2, 'D': 2})
('B', {'B': 0, 'G': 1, 'D': 2})
('C', {'C': 0, 'D': 1})
('D', {'D': 0})
('E', {'E': 0, 'F': 1, 'B': 2, 'G': 3, 'D': 4})
('F', {'F': 0, 'B': 1, 'G': 2, 'D': 3})
('G', {'G': 0, 'D': 1})

Puedes procesar e generador como desees para obtener una salida más acorde a tus necesidades.

import itertools
from typing import Generator, List, Optional, Tuple

import networkx as nx


class Grafo:

    def __init__(self, verts: List[str], conexs: List[Tuple[str, str]]) -> None:
        self._vertices = verts
        self._conexiones = conexs
        self._grafo = nx.DiGraph()
        self._grafo.add_nodes_from(self._vertices)
        self._grafo.add_edges_from(self._conexiones)

    def distancia_minima(self, nodo_a: str, nodo_b: str) -> Optional[int]:
        try:
            return nx.dijkstra_path_length(self._grafo, nodo_a, nodo_b)
        except (nx.exception.NodeNotFound, nx.exception.NetworkXNoPath):
            return None

    def distancias_minimas(self) -> Generator[Tuple[str, str, int], None, None]:
        dists_gen = nx.all_pairs_dijkstra_path_length(self._grafo)
        for nodo_a, distancias in dists_gen:
            del distancias[nodo_a] # Distancia al propio nodo_a
            for nodo_b, distancia in distancias.items():
                yield (nodo_a, nodo_b, distancia)


if __name__ == "__main__":
    vertices = ['A', 'B', 'C', 'D', 'E','F', 'G']
    conexiones = [
        ('A', 'B'), ('A', 'C'),('C','D'), ('E','F'),
        ('F','B'), ('B', 'G'),('G', 'D')
        ]

    grafo = Grafo(vertices, conexiones)
    print(f'Distancia mínima entre F y D: {grafo.distancia_minima("F", "D")}')

    print(f'{"-" * 79}\nDistancias mínimas entre nodos conectados\n{"-" * 79}')
    for nodo_a, nodo_b, distancia in grafo.distancias_minimas():
        print(f"Distancia mínima entre {nodo_a} y {nodo_b}: {distancia}")
Distancia mínima entre F y D: 3
-------------------------------------------------------------------------------
Distancias mínimas entre nodos conectados
-------------------------------------------------------------------------------
Distancia mínima entre A y B: 1
Distancia mínima entre A y C: 1
Distancia mínima entre A y G: 2
Distancia mínima entre A y D: 2
Distancia mínima entre B y G: 1
Distancia mínima entre B y D: 2
Distancia mínima entre C y D: 1
Distancia mínima entre E y F: 1
Distancia mínima entre E y B: 2
Distancia mínima entre E y G: 3
Distancia mínima entre E y D: 4
Distancia mínima entre F y B: 1
Distancia mínima entre F y G: 2
Distancia mínima entre F y D: 3
Distancia mínima entre G y D: 1

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.