El camino más corto de Dijkstra con la limitación máxima de los nodos intermedios -- python campo con algorithm campo con python-2.x camp codereview Relacionados El problema

Dijkstra's shortest path with max intermediate nodes limitation


0
vote

problema

Español

Supongo que desea calcular la ruta más corta de un nodo a todos los otros nodos, con la restricción de nodos intermedios no puede ser más que un número dado.

Mi idea principal es, siguiendo cómo funciona el algoritmo de Dijkstra, con solo la excepción que al actualizar la ruta más corta, si veo los nodos intermedios de ruta más corta excede el número dado, saldare la actualización. Más detalles, consulte esta línea and len(self.shortest_path[shortest_node_so_far]+[n[0]])-1 <= max_path_stop

Aquí está mi implementación, se aprecian cualquier consejo sobre mejoras de rendimiento en términos de complejidad de tiempo de algoritmo, errores de código o estilo de código.

Funda de prueba es del diagrama de Wikipedia ( https://en.wikipedia.org/wiki/ DIJKSTRA% 27S_ALGORITHM )

Código fuente en Python 2.7 ,

  from collections import defaultdict class Graph:     def __init__(self):         self.connections = defaultdict(list)         self.visited = set()         self.shortest_path = defaultdict(list)         self.shortest_path_distance = defaultdict(lambda : float('inf'))     def add_edge(self, edge):         self.connections[edge[0]].append((edge[1], edge[2]))         self.connections[edge[1]].append((edge[0], edge[2]))     def calculate_shortest_path(self, cur, max_path_stop):         self.visited.add(cur)         self.shortest_path[cur] = [cur]         self.shortest_path_distance[cur] = 0         for n,d in self.connections[cur]:             self.shortest_path_distance[n] = d             self.shortest_path[n].append(cur)             self.shortest_path[n].append(n)         while (len(self.visited) < len(self.connections.keys())):             shortest_so_far = float('inf')             shortest_node_so_far = None             for n,d in self.shortest_path_distance.items():                 if n in self.visited:                     continue                 if d <= shortest_so_far:                     shortest_node_so_far = n                     shortest_so_far = d             self.visited.add(shortest_node_so_far)             for n in self.connections[shortest_node_so_far]:                 if self.shortest_path_distance[shortest_node_so_far] + n[1] < self.shortest_path_distance[n[0]]                          and len(self.shortest_path[shortest_node_so_far]+[n[0]])-1 <= max_path_stop:                     self.shortest_path_distance[n[0]]=self.shortest_path_distance[shortest_node_so_far] + n[1]                     self.shortest_path[n[0]]=self.shortest_path[shortest_node_so_far]+[n[0]] if __name__ == "__main__":     g = Graph()     edges = [(1,2,7),(1,3,9),(1,6,14),(2,3,10),(3,6,2),(5,6,9),(5,4,6),(3,4,11),(2,4,15)]     for e in edges:         g.add_edge(e)     g.calculate_shortest_path(1,2)     print g.shortest_path     print g.shortest_path_distance   
Original en ingles

Suppose want to calculate the shortest path from one node to all other nodes, with the restriction of intermediate nodes cannot be more than a given number.

My major idea is, following how Dijkstra's algorithm works, with only the exception that when updating shortest path, if I see shortest path intermediate nodes exceeds the given number, I will skip the update. More details, refer to this line and len(self.shortest_path[shortest_node_so_far]+[n[0]])-1 <= max_path_stop

Here is my implementation, any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are appreciated.

Test case is from wikipedia diagram (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

Source code in Python 2.7,

from collections import defaultdict class Graph:     def __init__(self):         self.connections = defaultdict(list)         self.visited = set()         self.shortest_path = defaultdict(list)         self.shortest_path_distance = defaultdict(lambda : float('inf'))     def add_edge(self, edge):         self.connections[edge[0]].append((edge[1], edge[2]))         self.connections[edge[1]].append((edge[0], edge[2]))     def calculate_shortest_path(self, cur, max_path_stop):         self.visited.add(cur)         self.shortest_path[cur] = [cur]         self.shortest_path_distance[cur] = 0         for n,d in self.connections[cur]:             self.shortest_path_distance[n] = d             self.shortest_path[n].append(cur)             self.shortest_path[n].append(n)         while (len(self.visited) < len(self.connections.keys())):             shortest_so_far = float('inf')             shortest_node_so_far = None             for n,d in self.shortest_path_distance.items():                 if n in self.visited:                     continue                 if d <= shortest_so_far:                     shortest_node_so_far = n                     shortest_so_far = d             self.visited.add(shortest_node_so_far)             for n in self.connections[shortest_node_so_far]:                 if self.shortest_path_distance[shortest_node_so_far] + n[1] < self.shortest_path_distance[n[0]] \                         and len(self.shortest_path[shortest_node_so_far]+[n[0]])-1 <= max_path_stop:                     self.shortest_path_distance[n[0]]=self.shortest_path_distance[shortest_node_so_far] + n[1]                     self.shortest_path[n[0]]=self.shortest_path[shortest_node_so_far]+[n[0]] if __name__ == "__main__":     g = Graph()     edges = [(1,2,7),(1,3,9),(1,6,14),(2,3,10),(3,6,2),(5,6,9),(5,4,6),(3,4,11),(2,4,15)]     for e in edges:         g.add_edge(e)     g.calculate_shortest_path(1,2)     print g.shortest_path     print g.shortest_path_distance 
        

Lista de respuestas

2
 
vote

Si aplica su algoritmo dos veces, como en

          g.calculate_shortest_path(1,3)         ....         g.calculate_shortest_path(1,2)   

fallaría mal.

La razón es que visited1 , shortest_path2 99887766555443333 no es, y no puede ser, una propiedad de Graph (especialmente visited ). Son propiedades efímeras de un recorrido particular.

Cuestionablemente shortest_path6705443336 y shortest_path_distance podría hacerse propiedades de un vértice para permitir cierta optimización; No estoy muy seguro de que valga la pena esfuerzo.

 

If you apply your algorithm twice, as in

        g.calculate_shortest_path(1,3)         ....         g.calculate_shortest_path(1,2) 

it would fail badly.

The reason is that visited, shortest_path, and shortest_path_distance are not, and cannot be, a property of Graph (especially visited). They are ephemeral properties of a particular traversal.

Questionably shortest_path and shortest_path_distance could be made properties of a vertex to allow for some optimization; I not quite sure it worths effort.

 
 
     
     

Relacionados problema

10  Protocolo de red usando TCP, enviando imágenes a través de sockets  ( Network protocol using tcp sending images through sockets ) 
Me gustaría preguntar sobre su opinión sobre mi código. La idea es simple: diseñé mi propio protocolo, donde el cliente le pregunta al servidor sobre la image...

6  Valores coincidentes de la tabla HTML para actualizar los valores en Pandas DataFrame  ( Matching values from html table for updating values in pandas dataframe ) 
Esto es más un ejercicio para que me utilice a Pandas y sus cuadros de datos. Para aquellos que no escucharon de él: Panda es un paquete de Python que prop...

1  Foldify - Una herramienta de carpeta de Python Tree Tree  ( Foldify a python folder tree manager tool ) 
El objetivo era crear una herramienta para ayudar a administrar las estructuras de las carpetas y permitirme crear plantillas de estas carpetas y almacenarlas...

4  Uso eficiente de la expresión regular y la manipulación de cadenas  ( Efficient use of regular expression and string manipulation ) 
La siguiente es mi solución a java vs c ++ . Creo que la forma en que he usado, la biblioteca de RE es ineficiente, y es posible erróneas, ya que estoy obten...

3  Seleccione Quick - Shuffle para hacer una clasificación más rápida  ( Quick select shuffle to make sorting faster ) 
Estoy tratando de usar el shuffle para mejorar el peor caso del escenario de selección rápida (por ejemplo, cada vez, el valor de pivote seleccionado es el má...

6  Comprobando una cuadrícula de palabras  ( Checking a word grid ) 
Escribí este programa donde puede ingresar x cantidad de palabras que de longitud x que comprueba si la cuadrícula se formó son las mismas palabras vertic...

4  Atomas Clone en Python  ( Atomas clone in python ) 
Aquí está mi clon de mierda de atomas , un juego de rompecabezas donde combina pequeños átomos en otros más valiosos. 9988776655544337 ¿Hay algún códig...

3  Usuario rápido para algunos números, luego imprime el máximo y min  ( Prompt user for some numbers then print the max and min ) 
La función de este programa está solicitando repetidamente a un usuario para números enteros hasta que el usuario ingrese en 'done' . Una vez que se ingresa ...

2  Dos formas de aleatorias aleatoriamente las tarjetas  ( Two ways to randomly shuffle cards ) 
Aquí hay dos implementaciones que escribí para aleatorizar las tarjetas. El primer método ( dt5 ) Selecciona una tarjeta aleatoria, luego lo quita al frent...

1  Una clase con un puntero de función en lugar de un generador  ( A class with a function pointer instead of a generator ) 
Estoy construyendo archivos Tikz, un PDF para cada imagen que tengo. El propósito es agregar texto a cada uno por separado. Las imágenes son LEGION, así que c...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos