Python: come scoprire se esiste un percorso tra 2 nodi in un grafico?

Question

Sto usando il pacchetto networkx di Python.

Answer 1

>>> import networkx as nx 
>>> G=nx.empty_graph() 
>>> G.add_edge(1,2) 
>>> G.add_edge(2,3) 
>>> G.add_edge(4,5) 
>>> nx.path.bidirectional_dijkstra(G,1,2) 
(1, [1, 2]) 
>>> nx.path.bidirectional_dijkstra(G,1,3) 
(2, [1, 2, 3]) 
>>> nx.path.bidirectional_dijkstra(G,1,4) 
False 
>>> nx.path.bidirectional_dijkstra(G,1,5) 
False 
>>> 

È anche possibile utilizzare il risultato come un valore booleano

>>> if nx.path.bidirectional_dijkstra(G,1,2): print "path exists" 
... 
path exists 
>>> if nx.path.bidirectional_dijkstra(G,1,4): print "path exists" 
... 
>>> 

Answer 2

• dijkstra_path(G, source, target)

  restituisce il percorso più breve dall'origine alla destinazione in un grafo pesato G.

Answer 3

Usa

shortest_path(G, source, target) 

o uno dei metodi più breve Path. Stai alla larga dai metodi che restituiscono i percorsi tra tutti i nodi, tuttavia se hai solo due nodi specifici da testare per la connettività.

Answer 4

Utilizzando una struttura dati insieme disgiunto:

Creare un singoletto impostato per ogni vertice nel grafico, quindi sindacali gli insiemi contenenti ciascuna della coppia di vertici per ogni bordo nel grafico.

Infine, si sa che esiste un percorso tra due vertici se si trovano nello stesso set.

Vedere la pagina wikipedia sulla struttura di dati del set disgiunto.

Questo è molto più efficiente dell'utilizzo di un algoritmo di individuazione dei percorsi.

Answer 5

per verificare se v'è un percorso tra due nodi di un grafo -

>>> import networkx as nx 
>>> G=nx.Graph() 
>>> G.add_edge(1,2) 
>>> G.add_edge(2,3) 
>>> nx.has_path(G,1,3) 
True 
>>> G.add_edge(4,5) 
>>> nx.has_path(G,1,5) 
False 

Per ulteriori informazioni, fare riferimento has_path — NetworkX 1.7 documentation