**Dijkstra's algorithm**

Is a weighted graph G = (V, A), where V is the set of vertices, A the set of arcs and let L [i, j] its adjacency matrix. We calculate the shortest path between a vertex vi taken as origin and each remaining vertex vj in the graph.

The classic Dijkstra algorithm works in stages, where each of them is adding a vertex to the set D represents those vertices is known for its distance from the vertex origin. Initially the set D contains only the origin vertex.

is possible to raise the Dijkstra algorithm in terms of dynamic programming , and thus take advantage of the method design and the benefits this technology offers.

First, note that it is possible to apply the principle of optimal in this case: if the shortest path from vi to vj is a vertex v k as an intermediate, partial roads saw vk and vk to vj must be a minimum turn.

will call D (j) the vector containing the optimal path from the source vertex i = 1 to each vertex vj, 2 <=j <=n, siendo n el número de vértices. Inicialmente D contiene los arcos L(1,j), o bien ∞ si no existe el arco. A continuación, y para cada vértice vk del grafo con k <> 1, repeat:

Thus the algorithm that solves

problem can be implemented as follows:

CONST n = ..., (* number of vertices of the graph *)

TYPE MATRIX = ARRAY [1 .. n], [1 .. n] OF CARDINAL;

BRAND = ARRAY [1 .. n] OF BOOLEAN; (* elements already considered *)

SOLUTION = ARRAY [2 .. n] OF CARDINAL;

Dijkstra

PROCEDURE (VAR L: MATRIX; VAR D: SETTLEMENT )

var i, j, retail, pos, s: CARDINAL; S: BRAND;

BEGIN FOR i: = 2 TO n DO

S [i]: = FALSE;

D [i]: = L [1 , i]

END;

S [1]: = TRUE;

FOR i: = 2 TO n-1 DO

lower: = Menor (D, S, pos);

S [pos]: = TRUE;

FOR j: = 2 TO n DO NOT

IF (S [j]) THEN

D [j]: = Min2 (D [j], D [pos] + L [pos, j]) END

;

END;

Dijkstra

END END;

Minor Role is the calculated minimum

recurrence expression that defines the solution of the problem: Minor

PROCEDURE (VAR D: SETTLEMENT; VAR S: LABEL, VAR pos: CARDINAL)

: CARDINAL;

lower VAR i: CARDINAL ;

lower

BEGIN: = MAX (CARDINAL) pos: = 1;

FOR i: = 2 TO n DO NOT

IF (S [i]) THEN IF

D [i]

lower: = D [i ], pos: = i

END END END

;

less

RETURN END Minor

The time complexity of the algorithm is O (n2), where O (n) space complexity. No substantial gain in efficiency through the use of this technique with the greedy approach algorithm, yet we will win in simplicity of design and implementation of the solution from problem statement.