El camino más corto entre un punto y cada uno de los otros puntos

Question

Estoy tratando de averiguar cómo encontrar todos los caminos más cortos desde cada punto y cada nodo de una línea a los otros puntos y nodos de líneas de este mapa.

He intentado hacerlo en Python usando NetworkX. Para probarlo, recorté el mapa y traté de buscar sólo los caminos más cortos de cada nodo de una línea a todos los demás nodos de otras líneas de este mapa:

Con esa red de carreteras, tengo 214 nodos (lo que debería resultar en 214x214 caminos más cortos, creo). He intentado hacer el gráfico de la red de carreteras con este código:

#Create the network graph
G = nx.DiGraph()
for k,v in idict.items():
    G.add_edge(v[0],v[1], weight = v[2]) # v[0] = first (x,y) of a linestring, v[1] = last (x,y) of a linestring, v[2] = distance
    G.add_edge(v[1],v[0], weight = v[2]) #  return path

len(G.edges())

pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos = pos, node_size=20,arrows = True)
nx.draw_networkx_edges(G, pos = pos)
plt.show()

Y el resultado muestra:

También he tratado de aplicar la función warshall de Networkx Floyd para calcular todos los caminos más cortos de cada punto a otro punto, pero algunos de los resultados regresan al infinito (ya que creo que dice que no se encuentra ningún camino entre los puntos, mientras que en realidad todos los caminos están conectados). En total, sólo vuelve a unos 1720 caminos más cortos

¿Cómo debo proceder para tener el camino más corto de cada nodo a todos los demás nodos del mapa?

Answer 1

NetworkX all_shortest_paths o single_source_dijkstra

Hay que calcular todos los caminos más cortos desde el origen y luego resumir los pesos de las aristas de cada camino. También estoy absolutamente seguro de que hay una manera mucho más simple de hacer esto porque el algoritmo Dejkstra calcula todos los caminos en el gráfico para devolver uno solo. Así que no es necesario calcular de nuevo.

Answer 2

Desgraciadamente, la insinuación de Ahlfors es muy engañosa, y de hecho hay una forma más sencilla de resolver este problema, sobre todo porque a estas alturas del libro Ahlfors ha demostrado los teoremas de Mittag-Leffler y Weierstrass.

Dejemos que $g$ sea una función entera con ceros simples en $a_n$ . Recordemos que el Teorema de Mittag-Leffler no sólo afirma la existencia de funciones meromórficas con polos en $a_n$ pero nos permite controlar la parte singular de la función en cada $a_n$ . Así que dejemos $h$ sea una función meromorfa sobre $\mathbb{C}$ con postes simples en cada $a_n$ con la parte de singuar $c_n/(z-a_n)$ . Entonces $f:=gh$ tiene las propiedades deseadas.

Answer 3

Primero hay que definir qué se entiende por camino más corto. Si no ponderas tu grafo (G), el camino más corto es simplemente el camino que conecta los nodos que pasa por el menor número de otros nodos. Si quieres incorporar la longitud real de las líneas, necesitas crear un grafo ponderado:

# Compute weights
weights = lengths of each link in idict.items # square root of sum of squares or whatever

#Create the network graph
G = nx.Graph()
for k,v, wt in zip(idict.items(), weights):
    G.add_edge(v[0],v[1], weight = wt) 

Tenga en cuenta que, dado que su gráfico aparentemente no tiene direccionalidad, no debería utilizar un DiGraph. Un gráfico normal debería ser suficiente. Ahora G contiene enlaces ponderados, y puedes utilizar los algoritmos dijkstra para encontrar los caminos más cortos.

Debería consultar esta página para conocer sus opciones: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html Desplácese hasta "Algoritmos del camino más corto para grafos pesados".

Por su pregunta, parece que querrá uno de los all_pairs_xxx -- La elección depende del resultado que se quiera obtener. Si quiere los nodos reales a lo largo de cada camino más corto, utilice all_pairs_dijkstra_path . Si sólo necesita las longitudes, utilice all_pairs_dijkstra_path_length . Si necesita ambos, utilice all_pairs_dijkstra .

Tenga en cuenta que todas estas funciones devuelven un iterador: los caminos más cortos no se calculan realmente hasta que se descompone el iterador. Esto significa que estas funciones se calcularán muy rápidamente, pero el verdadero trabajo pesado ocurre después de desempaquetarlas. Puedes descomprimirlas de forma sencilla:

blah = nx.all_pairs_dijkstra_path(G)
shortest_paths = list(blah)

shortest_paths debe tener la misma longitud que el número de nodos de G.

Tenga en cuenta que hay cierta redundancia en este enfoque, y no estoy seguro de si networkX aprovecha el hecho de que el camino más corto de n0->n1 es el mismo que n1->n0 para un grafo no dirigido.