Pourquoi l'algorithme de Dijkstra fonctionne-t-il?

L'algorithme de Dijkstra sélectionne le sommet avec le moindre coût de chemin jusqu'à présent, car un chemin à travers un autre sommet est au moins aussi coûteux qu'un chemin à travers le sommet avec le moins de coût de chemin.

Visiter n'importe quel autre sommet, donc, si c'est plus coûteux (ce qui est tout à fait possible) nécessiterait de visiter non seulement cet autre sommet, mais aussi celui avec le moins de coût de chemin jusqu'à présent, donc vous devriez visiter plus de Sommets avant de trouver le chemin le plus court. En fait, vous serait la fin de la avec l'algorithme Bellman-Ford Si vous avez fait cela.

Je devrais aussi ajouter que le Sommet n'a pas de poids, c'est le bord qui a un poids. La clé pour un sommet donné est le coût du chemin le plus court trouvé jusqu'à ce sommet à partir du sommet source.

La raison pour laquelle l'algorithme de Dijsktra fonctionne comme il le fait est en partie car il exploite le fait que le chemin le plus court entre le nœud u et w qui inclut le point v contient également le chemin le plus court de u à v et de v à w. S'il existait quelque chose de plus court entre u et v, alors ce ne serait pas le chemin le plus court.

Pour vraiment comprendre pourquoi l'algorithme de Dijkstra fonctionne, regardez dans les bases de la programmation dynamique , semble difficile mais c'est vraiment assez facile de comprendre les principes.

Il aime gourmand strategy.My l'anglais n'est pas good.It traduit par google.Si vous ne comprenez pas,je suis vraiment désolé.

Algorithme de Dijkstra, A G de S à tous les sommets de la longueur de chemin la plus courte. Nous supposons que chaque sommet de G dans V a reçu un drapeau L (V), c'est soit un nombre, soit ∞. Supposons que P est l'ensemble des sommets de G, P contient S, pour satisfaire:

A) Si V est P, alors L (V) de V S à la longueur du chemin le plus court, et l'existence D'un tel V de S à la chemin le plus court: chemin sur les sommets dans P dans

B) Si V N'appartient pas à P, alors L (V) de S à V satisfait aux restrictions suivantes sur la longueur du chemin le plus court: V est le seul chemin P N'appartient pas au sommet.

Nous pouvons utiliser l'induction pour prouver P algorithme Dijkstra en ligne avec la définition ci-dessus de la collection:

1) Lorsque le nombre d'éléments de P = 1, P correspond à la première étape de l'algorithme, P = (S), est clairement satisfaite.

2) Supposons que P est k, le nombre d'éléments, p satisfaire la définition ci-dessus, voir l'algorithme ci-dessous la troisième étape

3) P Dans et le premier à savoir n'est pas marqué avec le Sommet minimum U, marqué comme L (U), peut être prouvé de S à U de U en dehors du chemin le plus court, en plus de P ne contient pas les éléments n'appartiennent pas.

Parce que s'il y a en dehors des autres sommets sauf U, alors le chemin le plus court vers S, P1, P2 ... Pn, Q1, Q2 ... Qn, U (P1, P2 ... Pn est P; Q1, Q2,... Qn n'appartient pas à P), de la nature de B) La longueur du chemin le plus court L (Q1) + chemin (Q1, U)> L (U).

Qui est supérieur à S, P1, P2 ... Pn, U de la longueur du canal L (U), n'est pas le chemin le plus court. Par conséquent, de la S à L'U de U en dehors du chemin le plus court, en plus de P ne contient pas les éléments n'appartiennent pas à U de S à la longueur du chemin le plus court de la L (U) est donnée.

U est ajouté à P sous la forme P ', clairement P' pour répondre à la nature du A).

Prendre V n'appartient pas à P ', n'appartient évidemment pas à V P, puis de S à V sauf le chemin le plus court et rencontrer tous les sommets en dehors de V dans P' dans le chemin il y a deux possibilités, I) contient U, ii) ne contient pas U.

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

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

Évidemment, les deux sont donnés dans le plus petit V de S pour répondre à l'accès minimum et l'addition extérieure à tous les sommets sont V P 'de longueur.

La troisième étape à l'algorithme donné en P ' avec K + 1 éléments et répondre à la A), B).

Par la proposition d'induction peut permettre.

Ici la source.

Il vérifie d'abord le chemin avec le poids le plus bas car il est le plus probable (sans informations supplémentaires) de réduire le nombre de chemins vérifiés. Par exemple:

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

Si le but est d'aller de a à e, nous n'avons même pas besoin de vérifier le coût de:

a->b->c->e

Parce que nous savons que c'est au moins 20 donc nous savons que ce n'est pas optimal car il y a déjà un autre chemin avec un coût de 12. Vous pouvez maximiser cet effet en vérifiant d'abord les poids les plus bas. C'est la même?) de la façon dont minimax fonctionne dans les échecs et d'autres jeux pour réduire le facteur de ramification de l'arbre de jeu.

L'algorithme de Dijsktra est un algorithme gourmand qui suit l'heuristique de résolution de problèmes de faire le choix localement optimal à chaque étape avec l'espoir de trouver un optimum global.

Pour comprendre le concept de base de cet algorithme, j'ai écrit ce code pour vous. Il y a une explication de la façon dont cela fonctionne.

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()