Algorithm Design and Complexity

Imagine preview
(7/10)

Aceasta fituica rezuma Algorithm Design and Complexity.
Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier pdf de 4 pagini .

Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, o poti descarca. Ai nevoie de doar 4 puncte.

Domeniu: Calculatoare

Extras din document

24.3 Dijkstra's algorithm Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. In this section, therefore, we assume that w(u, v) e 0 for each edge (u, v) _ E. As we shall see, with a good implementation, the running time of Dijkstra's algorithm is lower than that of the Bellman- Ford algorithm. Dijkstra's algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u _ V – S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u. In the following implementation, we use a min-priority queue Q of vertices, keyed by their d values. DIJKSTRA(G, w, s) 1 INITIALIZE-SINGLE-SOURCE(G, s) 2 S  Ø 3 Q  V[G] 4 while Q ` Ø 5 do u  EXTRACT-MIN(Q) 6 S  S _{u} 7 for each vertex v _ Adj[u] 8 do RELAX(u, v, w) Dijkstra's algorithm relaxes edges as shown in Figure 24.6. Line 1 performs the usual initialization of d and À values, and line 2 initializes the set S to the empty set. The algorithm maintains the invariant that Q = V - S at the start of each iteration of the while loop of lines 4- 8. Line 3 initializes the min-priority queue Q to contain all the vertices in V ; since S = Ø at that time, the invariant is true after line 3. Each time through the while loop of lines 4-8, a vertex u is extracted from Q = V - S and added to set S, thereby maintaining the invariant. (The first time through this loop, u = s.) Vertex u, therefore, has the smallest shortest-path estimate of any vertex in V - S.

Fisiere in arhiva (1):

  • Algorithm Design and Complexity.pdf

Alte informatii

Fituici Algorithm Design and Complexity. FILS (Facultatea de Inginerie cu Predare in Limbi Straine). Anul V. Semestrul II.