Dijkstra’s algorithm

Dijkstra’s algorithm. Also called the minimum paths algorithm, it is an algorithm for determining the shortest path given a vertex origin to the rest of the vertices in a graph with weights on each edge. Its name refers to Edsger Dijkstra , who first described it in 1959 .

Summary

[ hide ]

  • 1 Applications
  • 2 Algorithm characteristics
  • 3 steps of the algorithm
  • 4 Algorithm execution
  • 5 End of the Execution Process
  • 6 Pseudocode
    • 1 Priority queue
    • 2 No priority queue
  • 7 External links

Applications

In multiple applications where graphs are applied, it is necessary to know the least cost path between two given vertices:

  • Distribution of products to a network of commercial establishments.
  • Distribution of postal mails.
  • Let G = (V, A) be a weighted directed graph.

The problem with the shortest path from one vertex to another is to determine the least cost path, from one vertex to another vertex v. The cost of a road is the sum of the costs (pesos) of the arches that make it up.

Algorithm characteristics

  • It is a greddy algorithm.
  • Work in stages, and take the best solution at each stage without considering future consequences.
  • The optimum found in one stage can be modified later if a better solution emerges.

Algorithm steps

Algorithm 24.1: Dijkstra’s algorithm. Initialization.

  • Let V be a set of vertices of a graph.
  • Let C be a cost matrix of the edges of the graph, where in C [u, v] the cost of the edge is stored between u and v.
  • Let S be a set that will contain the vertices for which the minimum path is already determined.
  • Let D be a one-dimensional array such that D [v] is the cost of the minimum path from the origin vertex to vertex v.
  • Let P be a one-dimensional array such that P [v] is the predecessor vertex of v on the minimum path we have built.
  • Let the origin vertex be vinitic. Remember that the Dijkstra algorithm determines the minimum paths that exist starting from one origin vertex to the rest of the vertices.

Step 1. S ← {vinicial} // Initially S will contain the vertex // origin

Step 2. For each v∈V, v ≠ vinicial, do

2.1. D [v] ← C [vinicial, v] // Initially the cost of the // minimum path of vinicial av is what is contained in // the cost matrix

2.2. P [v] ← vinicial // Initially, the // predecessor of v in the minimal path built // so far is vinicial

Step 3. While (V – S ≠ ∅) do // As long as there are vertices for // for which the // minimum path has not been determined

3.1. Choose a vertex w∈ (VS) such that D [w] is the minimum.

3.2. S ← S ∪ {w} // We add w to the set S, since we already // have the minimum path to w

3.3. For each v∈ (VS) do

3.3.1. D [v] ← min (D [v], D [w] + C [w, v]) // You choose, between // the minimum path to v that you have // ​​so far, and the path to v // passing through w by its minimum path, // the least expensive.

3.3.2. If min (D [v], D [w] + C [w, v]) = D [w] + C [w, v] then P [v] ← w // If you choose to go for w then // the predecessor of v at the moment is w

Step 4. End

Algorithm execution

  • Step 1: Initialization
  • Step 2: Choose a vertex w V – {A} such that D [w] is minimum, and add w to the solution set S
  • Step 3: every v {C, D, E} do D [v] ← min (D [v], D [w] + C [w, v])

 

  • Step 4: Choose a vertex w V – {A, B} such that D [w] is minimum, and add w to the solution set S.
  • Step 5: For each v {C, E} do D [v] ← min (D [v], D [w] + C [w, v]

File: Something09.JPG

  • Step 6: Choose a vertex w V – {A, B, D} such that D [w] is minimal, and add w to the solution set S.
  • Step 7: For each v {E} do D [v] ← min (D [v], D [w] + C [w, v]

 

  • Step 8: Choose a vertex w V – {A, B, D, C} such that D [w] is minimal, and add w to the solution set S.

End of the Execution Process

After step 8 we have the following situation:

  • The set of vertices V = {A, B, C, D, E}
  • The set of vertices for which the minimum path S = {A, B, D, C, E} has already been determined

Therefore, as VS = Ø, the algorithm ends, since for each node of the graph, its minimum path has been determined. As a result of the execution of the algorithm we have:

D [B] D [C] D [D] D [E] P [B] P [C] P [D] P [E]

  10 50 30 60 ADAC

At the end of the execution of the Dijkstra algorithm, the costs of the minimum paths that start from the origin vertex to the rest of the vertices are stored in array D. Therefore, in our example, the minimum path from A to B has cost 10, the minimum path from A to C has cost 50, the minimum path from A to D has cost 30 and the minimum path from A to E has cost 60. .

Let’s see how the minimum paths can be obtained from the array of predecessors. The paths are reconstructed starting from the destination vertex until reaching the origin vertex.

MinimumPath (A, B) = AB since P [B] = A

Minimum Path (A, C) = ADC since P [C] = D and P [D] = A

MinimumPath (A, D) = AD since P [D] = A

Minimum Path (A, E) = ADCE since P [E] = C, P [C] = D and P [D] = A

Finally, the minimum path that includes all the vertices of the graph is ADCE.

Pseudocode

Priority queue

DIJKSTRA (Graph G, source_node s)

for u ∈ V [G] do

distance [u] = INFINITE

parent [u] = NULL

distance [s] = 0

add (tail, (s, distance [s]))

while queue is not empty do

u = extract_minimum (queue)

for all v ∈ adjacency [u] do

if distance [v]> distance [u] + weight (u, v) do

distance [v] = distance [u] + weight (u, v)

father [v] = u

add (tail, (v, distance [v]))

No priority queue

Dijkstra function (Graph G, node_output s)

// We will use a vector to save the distances from the output node to the rest integer distance [n]

// Initialize the vector with Boolean initial distances seen [n]

// vector of boleanos to control the vertices of which we already have the minimum distance

for each w ∈ V [G] do

If (there is no edge between s and w) then

distance [w] = Infinity // you can check the box with a -1 for example

If not

distance [w] = weight (s, w)

End yes

end for

distance [s] = 0

seen [s] = true

// n is the number of vertices that the Graph has

while (not_look_all_doing) do

vertex = take_the_minimum_of_vector distance and that is not seen;

seen [vertex] = true;

for each w ∈ successors (G, vertex) do

if distance [w]> distance [vertex] + weight (vertex, w) then

distance [w] = distance [vertex] + weight (vertex, w)

End yes

end for

end while

end function

 

Leave a Comment