Is Dijkstra greedy or dynamic

Dijkstra's algorithm

You just don't understand how the Dijkstra's algorithm? No problem! We'll see him Step by step at.

  • Dijkstra's algorithm
    in the text
  • Dijkstra's algorithm sequence based on an example
    in the text
  • Pseudocode of the Dijkstra algorithm
    in the text

Dijkstra's algorithm

The Dijkstra algorithm is a so-called Greedy algorithm. He will help you shortest respectively cheapest ways to calculate. The Edge weightsThis is what the costs to get from one point to the next are called allowed with the Dijkstra algorithm not negative be. But if so negative cost occur, you'd better get the Bellman-Ford algorithm apply.

Dijkstra's algorithm sequence based on an example

To understand the Dijkstra algorithm, let's look at a specific one example at!

Imagine you are planning your next trip. The question is how do you get yours the cheapest way to reach possible travel destinations can. For example, what's the quickest way to get away Nuremberg to Copenhagen? By getting over Hamburg or over Berlin driving?

Let's take a closer look at the graph. The Route AB has an edge weight of 100. That means you get to this cost of Place A to B.

That would be clarified. Then we can now start calculating the example by hand. Of course you can also do it in Implement Java, the corresponding Pseudocode can be found below in our article.

initialization

  • First you have to do the algorithm initialize.
  • The best thing to do is put one table to keep track of things. In the first column you enter the respective iteration in which you are. For each knot you then give the respective one costs and the direct predecessor In the last column you can manage your approach. This will help you to have a good overview.
  • The Cost to the starting node be zero. You're already home.
  • To your possible travel locations is still no known way. That's why you first evaluate the costs Infinite. It doesn't stay that way, of course. Little by little these become Improved costs.
  • Now you need one Queue. All nodes that you have already found will be inserted into this. Since you only have yours so far Starting node do you know you add this to yours first Queue

Iteration 1

Let's come to first iteration.

  • Because in the queue only an element is, you select this and look at the direct successor. From the start node, the Node B and D. can be achieved.
  • The cost to dated Starting node according to B to come amount 100. As Predecessor of node B are you wearing the Starting node in your table.
  • That's how you go with Node D The costs to get from the starting node to D are 50. And as a predecessor, you also wear that first knot a.
  • You have now considered the successors of the starting node. You can use it as a mark done.
  • The two Successor node do you take in yours Queue

Iteration 2

It goes on with Iteration 2.

  • Now you choose that nodeyou with the lowest cost get out of your queue. That is here Node D. Now look at them successor.
  • The cost of node B do not change. The direct way from the start node cheaper than the detour via node D.
  • The new costs of node E are now 300. Wear that here too direct predecessor
  • Add your queue for the Node E. Node B is already in the queue.
  • Node D you have to from now on do not look any further and can use it as mark done.

Iteration 3

This is how you proceed in the next iteration.

  • The cost to Node C to be achieved 200 and the Predecessor is B.
  • At Node E does not change anything. Update your queue here too by adding nodes B. as done mark and C in the queue record.

Iteration 4

  • In iteration 4, the Successor to node C That's just node E. But you can see that you Node E cheaper reach if you the way via B and C choose. That means you get new cost of 250 and C as the new predecessor.
  • Also Node E you can now as done

Iteration 5

Very good! You have all nodes processed! So you can't put another knot in the Queue record, so it is empty. That leads to Abort the algorithm.

Pooh that was a lot now! We did it right away. Let's just take a quick look at what these are for you table now actually says. The Read off from the table recursive: Let's take a closer look at node E, for example. Node E will with Total cost of 250 reached. The predecessor is Node C. The best way to reach this is via B.. And you can get there directly from the starting node. The shortest way from Start node to E so leads via nodes B and C..

Top! The next Semester break can come! Because in the same way, you can now find out how you can best from Nuremberg to Copenhagen come

Excellent! We have ours Example calculated and you know how that too Result from the tableread is.

Pseudocode of the Dijkstra algorithm

You want yourself Save work and the Dijkstra algorithm not every time laboriously calculate by hand? No problem! For example, you can use it in Implement Java. It is helpful to do this in advance Pseudocode of the algorithm.

initialization

Add start node to queue W.
Set of completed nodes E = ∅
Rate the cost of the start node as 0
Evaluate costs for all nodes except starting nodes with ∞

Iterations

as long as W ≠ ∅
choose node k with the lowest cost to be the starting node
add k to W.
compute new costs for all successors j of k that are not elements of E.
if Costs to j over k are lower
update costs to j
update predecessors of j
add j to W.
remove k from W
add k to E.
if W = ∅
Algorithm ended