Open Brokerga Eaccount Hong Kong

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.