Arhitectura Calculatoarelor - Intel vs AMD
Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D,...
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
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.
Fituici Algorithm Design and Complexity. FILS (Facultatea de Inginerie cu Predare in Limbi Straine). Anul V. Semestrul II.