I understand what Dijkstra's algorithm is, but I don't understand why it works.
When selecting the next vertex to examine, why does Dijkstra's algorithm select the one with the smallest weight? Why not just select a vertex arbitrarily, since the algorithm visits all vertices anyway?
You can think of Djikstra's algorithm as a water-filling algorithm (i.e. a pruned breadth-first search). At each stage, the goal is to cover more of the whole graph with the lowest-cost path possible. Suppose you have vertices at the edge of the area you've filled in, and you list them in terms of distance:
v0 <= v1 <= v2 <= v3 ...
Could there possibly be a cheaper way to get to vertex v1? If so, the path must go through v0, since no untested vertex could be closer. So you examine vertex v0 to see where you can get to, checking if any path through v0 is cheaper (to any other vertex one step away).
If you peel away the problem this way, you're guaranteed that your distances are all minimums, because you always check exactly that vertex that could lead to a shortest path. Either you find that shortest path, or you rule it out, and move on to the next vertex. Thus, you're guaranteed to consume one vertex per step.
And you stop without doing any more work than you need to, because you stop when your destination vertex occupies the "I am smallest" v0 slot.
Let's look at a brief example. Suppose we're trying to get from 1 to 12 by multiplication, and the cost between nodes is the number you have to multiply by. (We'll restrict the vertices to the numbers from 1 to 12.)
We start with 1, and we can get to any other node by multiplying by that value. So node 2 has cost 2, 3 has cost 3, ... 12 has cost 12 if you go in one step.
Now, a path through 2 could (without knowing about the structure) get to 12 fastest if there was a free link from 2 to 12. There isn't, but if there was, it would be fastest. So we check 2. And we find that we can get to 4 for cost 2, to 6 for 3, and so on. We thus have a table of costs like so:
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.
Okay, now maybe we can get to 12 from 3 for free! Better check. And we find that 3*2==6 so the cost to 6 is the cost to 3 plus 2, and to 9 is plus 3, and 12 is plus 4.
4 5 6 7 8 9 10 11 12
4 5 5 7 6 6 7 11 7
Fair enough. Now we test 4, and we see we can get to 8 for an extra 2, and to 12 for an extra 3. Again, the cost to get to 12 is thus no more than 4+3 = 7:
5 6 7 8 9 10 11 12
5 5 7 6 8 7 11 7
Now we try 5 and 6--no improvements so far. This leaves us with
7 8 9 10 11 12
7 6 8 7 11 7
Now, for the first time, we see that the cost of getting to 8 is less than the cost of getting to 7, so we had better check that there isn't some free way to get to 12 from 8. There isn't--there's no way to get there at all with integers--so we throw it away.
7 9 10 11 12
7 8 7 11 7
And now we see that 12 is as cheap as any path left, so the cost to reach 12 must be 7. If we'd kept track of the cheapest path so far (only replacing the path when it's strictly better), we'd find that 3*4 is the first cheapest way to hit 12.
Dijkstra's algorithm picks the vertex with the least path cost thus far, because a path through any other vertex is at least as costly as a path through the vertex with the least path cost.
Visiting any other vertex, therefore, if it is more costly (which is quite possible) would necessitate visiting not only that other vertex, but also the one with the least path cost thus far, so you would have to visit more vertices before finding the shortest path. In fact, you would end up with the Bellman-Ford algorithm if you did that.
I should also add that the vertex doesn't have a weight, it is the edge that has a weight. The key for a given vertex is the cost of the shortest path found thus far to that vertex from the source vertex.
The reason why Dijsktra's algorithm works the way it does is in part because it exploits the fact that the shortest path between node u and w that includes point v also contains the shortest path from u to v and from v to w. If there existed something shorter between u to v, then it wouldn't be the shortest path.
To really understand why Dijkstra's algorithm works, look into the basics of dynamic programming, sounds hard but it's really pretty easy to understand the principles.
It likes greedy strategy.My English is not good.It translates by google.If you don't understand,I am very sorry.
Dijkstra algorithm, a G from S to all vertices of the shortest path length. We assume that each vertex of G in V have been given a flag L (V), it is either a number, either ∞. Suppose P is the set of vertices of G, P contains S, to satisfy:
A) If V is P, then L (V) from V S to the length of the shortest path, and the existence of such V from S to the shortest path: path on the vertices in P in
B) If V does not belong to P, then L (V) from S to V satisfy the following restrictions on the length of the shortest path: V is the only path P does not belong to the vertex.
We can use induction to prove P Dijkstra algorithm in line with the above definition of the collection:
1) When the number of elements in P = 1, P corresponds to the first step in the algorithm, P = (S), is clearly satisfied.
2) Suppose P is k, the number of elements, P satisfy the above definition, see the algorithm below the third step
3) P in and the first to find out is not marked with the minimum vertex U, marked as L (U), can be proved from S to U of U outside the shortest path, in addition to P does not contain the elements do not belong.
Because if there is outside the other vertices except U, then the shortest path to S, P1, P2 ... Pn, Q1, Q2 ... Qn, U (P1, P2 ... Pn is P; Q1, Q2, ... Qn does not belong to P), from the nature of B) the shortest path length L (Q1) + PATH (Q1, U)> L (U).
Which is greater than S, P1, P2 ... Pn, U of the channel length L (U), is not the shortest path. Therefore, from the S to the U of U outside the shortest path, in addition to P does not contain the elements do not belong to U from S to the length of the shortest path from the L (U) is given.
U is added to P in the form P ', clearly P' to meet the nature of the A).
Take V does not belong to P ', obviously does not belong to V P, then from S to V except the shortest path and meet all the vertices outside V in P' in the path there are two possibilities, i) contains U, ii) does not contain U.
On i) S, P1, P2 ... Pn, U, V = L (U) + W (U, V)
ii) S, P1, P2 ... Pn, V = L (V)
Obviously the two are given in the smallest V from S to meet the minimum access and outside addition to all the vertices are V P 'in length.
The third step to algorithm given in P 'with k +1 elements and meet the A), B).
By the induction proposition may permit.
Here is the source.
It checks the path with the lowest weight first because this is most likely (without additional information) to reduce the number of paths checked. For example:
a->b->c cost is 20 a->b->d cost is 10 a->b->d->e cost is 12
If goal is to get from a to e, we don't need to even check the cost of:
a->b->c->e
Because we know it's at least 20 so we know it's not optimal because there is already another path with a cost of 12. You can maximize this effect by checking the lowest weights first. This is similar (same?) to how minimax works in chess and other games to reduce the branching factor of the game tree.
For understand the basic concept of this algorithm, I wrote this code for you. There is an explanation of how it works.
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()
whythe greedy algorithm is suitable... - M. Williams