investigacion - dijkstra algorithm

¿Por qué funciona el algoritmo de Dijkstra?

Question

Entiendo cuál es el algoritmo de Dijkstra , pero no entiendo por qué funciona.

Al seleccionar el siguiente vértice para examinar, ¿por qué el algoritmo de Dijkstra selecciona el que tiene el menor peso? ¿Por qué no simplemente seleccionar un vértice arbitrariamente, ya que el algoritmo visita todos los vértices de todos modos?

Answer 1

Comprueba la ruta con el peso más bajo primero porque es muy probable (sin información adicional) reducir el número de rutas marcadas. Por ejemplo:

a->b->c cost is 20 a->b->d cost is 10 a->b->d->e cost is 12

Si el objetivo es pasar de a a e, no es necesario que controlemos el costo de:

a->b->c->e

Porque sabemos que tiene al menos 20, por lo que sabemos que no es óptimo porque ya hay otra ruta con un costo de 12. Puede maximizar este efecto comprobando primero los pesos más bajos. Esto es similar (¿lo mismo?) A cómo funciona minimax en el ajedrez y otros juegos para reducir el factor de ramificación del árbol de juego.

Answer 2

El algoritmo de Dijkstra elige el vértice con el menor costo de ruta hasta el momento, porque una ruta a través de cualquier otro vértice es al menos tan costosa como una ruta a través del vértice con el menor costo de ruta.

Visitar cualquier otro vértice, por lo tanto, si es más costoso (lo cual es bastante posible) necesitaría visitar no solo ese otro vértice, sino también el que tiene el menor costo de ruta hasta el momento, por lo que tendría que visitar más vértices antes de encontrar el camino más corto. De hecho, terminarías con el algoritmo Bellman-Ford si lo hicieras.

También debo agregar que el vértice no tiene un peso, es el borde el que tiene un peso. La clave para un vértice dado es el costo de la ruta más corta encontrada hasta ahora para ese vértice desde el vértice fuente.

Answer 3

El algoritmo de Dijsktra es un algoritmo codicioso que sigue la heurística de resolución de problemas de hacer la elección localmente óptima en cada etapa con la esperanza de encontrar un óptimo global.

Answer 4

La razón por la cual el algoritmo de Dijsktra funciona de la manera que lo hace es en parte porque explota el hecho de que la ruta más corta entre el nodo u w que incluye el punto v también contiene la ruta más corta desde u hasta v de v hasta w . Si existiera algo más corto entre tú y v, entonces no sería el camino más corto.

Para entender realmente por qué funciona el algoritmo de Dijkstra, fíjese en los fundamentos de la programación dinámica , suena difícil pero es muy fácil entender los principios.

Answer 5

Le gusta la estrategia codiciosa. Mi inglés no es bueno. Se traduce por google. Si no entiende, lo siento mucho.

Algoritmo de Dijkstra, una G de S a todos los vértices de la longitud de camino más corta. Suponemos que a cada vértice de G en V se le ha dado una bandera L (V), o es un número, ya sea ∞. Supongamos que P es el conjunto de vértices de G, P contiene S, para satisfacer:

A) Si V es P, entonces L (V) desde VS hasta la longitud de la ruta más corta, y la existencia de tal V desde S hasta la ruta más corta: ruta en los vértices en P en

B) Si V no pertenece a P, entonces L (V) de S a V satisface las siguientes restricciones en la longitud de la ruta más corta: V es la única ruta P que no pertenece al vértice.

Podemos usar la inducción para probar el algoritmo P Dijkstra en línea con la definición anterior de la colección:

1) Cuando el número de elementos en P = 1, P corresponde al primer paso en el algoritmo, P = (S) está claramente satisfecho.

2) Suponga que P es k, el número de elementos, P satisface la definición anterior, vea el algoritmo debajo del tercer paso

3) P in y el primero en descubrir que no está marcado con el vértice mínimo U, marcado como L (U), se puede probar desde S hasta U de U fuera del camino más corto, además de que P no contiene los elementos no pertenecer.

Porque si hay fuera de los otros vértices excepto U, entonces el camino más corto hacia S, P1, P2 ... Pn, Q1, Q2 ... Qn, U (P1, P2 ... Pn es P; Q1, Q2, ... Qn no pertenece a P), de la naturaleza de B) la longitud del camino más corto L (Q1) + RUTA (Q1, U)> L (U).

Que es mayor que S, P1, P2 ... Pn, U de la longitud del canal L (U), no es la ruta más corta. Por lo tanto, desde el S hasta la U de U fuera del camino más corto, además de que P no contiene los elementos, no pertenece a U desde S hasta la longitud del camino más corto desde donde se da L (U).

U se agrega a P en la forma P '', claramente P'' para cumplir con la naturaleza de A).

Tomar V no pertenece a P '', obviamente no pertenece a VP, luego de S a V excepto el camino más corto y cumple todos los vértices fuera de V en P'' en el camino hay dos posibilidades, i) contiene U, ii) no contiene U.

En i) S, P1, P2 ... Pn, U, V = L (U) + W (U, V)

ii) S, P1, P2 ... Pn, V = L (V)

Obviamente, los dos se dan en la V más pequeña de S para cumplir con el acceso mínimo y la adición externa a todos los vértices son de longitud de PV ''.

El tercer paso al algoritmo dado en P ''con k +1 elementos y cumplir con A), B).

Por la propuesta de inducción puede permitir.

Aquí está la fuente .

Answer 6

Para entender el concepto básico de este algoritmo, escribí este código para ti. Hay una explicación de cómo funciona.

graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None
processed = []
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",/
graph["start"]["{}".format(node)]
while node is not None:
cost = costs[node]
print "Continue execution ..."
print "The weight of node {} is".format(node), cost
neighbors = graph[node]
if neighbors != {}:
print "The node {} has neighbors:".format(node), neighbors
else:
print "It is finish, we have the answer: {}".format(cost)
for neighbor in neighbors.keys():
new_cost = cost + neighbors[neighbor]
if costs[neighbor] > new_cost:
costs[neighbor] = new_cost
parents[neighbor] = node
processed.append(node)
print "This nodes we researched:", processed
node = find_lowest_cost_node(costs)
if node is not None:
print "Look at the neighbor:", node
# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)
import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

Answer 7

Puede pensar en el algoritmo de Djikstra como un algoritmo de llenado de agua (es decir, una búsqueda de amplitud de poda podada). En cada etapa, el objetivo es cubrir más de todo el gráfico con el camino de menor costo posible. Supongamos que tiene vértices en el borde del área que ha rellenado y los enumera en términos de distancia:

v0 <= v1 <= v2 <= v3 ...

¿Podría haber una forma más económica de llegar al vértice v1 ? Si es así, la ruta debe pasar por v0 , ya que ningún vértice no probado podría estar más cerca. Entonces, examina el vértice v0 para ver a dónde puedes llegar, verificando si cualquier ruta a través de v0 es más barata (a cualquier otro vértice a un paso).

Si quita el problema de esta manera, tiene la garantía de que sus distancias son mínimas, porque siempre verifica exactamente ese vértice que podría conducir al camino más corto. O encuentras el camino más corto, o lo descartas, y pasas al siguiente vértice. Por lo tanto, tiene la garantía de consumir un vértice por paso.

Y se detiene sin hacer más trabajo del necesario, porque se detiene cuando su vértice de destino ocupa el espacio "Soy el más pequeño" v0 .

Veamos un breve ejemplo. Supongamos que estamos tratando de obtener del 1 al 12 por multiplicación, y el costo entre nodos es el número que tiene que multiplicar. (Restringiremos los vértices a los números del 1 al 12 ).

Comenzamos con 1 , y podemos llegar a cualquier otro nodo multiplicando por ese valor. Así que el nodo 2 tiene un costo de 2 , 3 tiene un costo de 3 , ... 12 ha costado 12 si vas en un solo paso.

Ahora, un camino a través de 2 podría (sin conocer la estructura) llegar a 12 más rápido si hubiera un enlace libre de 2 a 12 . No lo hay, pero si lo hubiera, sería más rápido. Entonces comprobamos 2 . Y descubrimos que podemos llegar a 4 por costo 2 , a 6 por 3 , y así sucesivamente. Por lo tanto, tenemos una tabla de costos como esta:

3 4 5 6 7 8 9 10 11 12 // Vertex
3 4 5 5 7 6 9 7 11 8 // Best cost to get there so far.

De acuerdo, ahora tal vez podamos obtener 12 de 3 gratis! Mejor control. Y encontramos que 3*2==6 por lo que el costo de 6 es el costo de 3 más 2 , y para 9 es más 3 , y 12 es más 4 .

4 5 6 7 8 9 10 11 12
4 5 5 7 6 6 7 11 7

Lo suficientemente justo. Ahora probamos 4 , y vemos que podemos obtener 8 para un extra de 2 y 12 para un extra de 3 . De nuevo, el costo para llegar a 12 es más que 4 + 3 = 7 :

5 6 7 8 9 10 11 12
5 5 7 6 8 7 11 7

Ahora probamos 5 y 6 --no hay mejoras hasta el momento. Esto nos deja con

7 8 9 10 11 12
7 6 8 7 11 7

Ahora, por primera vez, vemos que el costo de llegar a 8 es menor que el costo de llegar a 7 , por lo que es mejor que verifiquemos que no haya alguna forma gratuita de obtener 12 de 8 . No hay, no hay forma de llegar allí con números enteros, así que lo tiramos.

7 9 10 11 12
7 8 7 11 7

Y ahora vemos que 12 es tan barato como cualquier camino restante, por lo que el costo para llegar a 12 debe ser 7 . Si hubiéramos hecho un seguimiento de la ruta más barata hasta el momento (solo reemplazando la ruta cuando es estrictamente mejor), encontraríamos que 3*4 es la primera forma más barata de llegar a 12 .