Multimedia Instructions (MMX)
2. MMX technology The MMX technology is designed to accelerate multimedia and communications...
Algorithm Design and Complexity
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.
Preview document
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.
Documente similare
-
Software Engineering
1. Introduction A. Definitions B. Main Activities Of A Software Project C. Software Development...
-
Proiectarea Aplicatiilor de Comert Electronic - Aplicatie de Food-Ordering
Progresele realizate recent în domeniile tehnologie-calculatoare, telecomunicatii si software,...
Procesare Distribuita
Aceste note de curs se bazeaza pe urmatoarele texte: 1. Distributed Computing , H. Attyia...
-
Microsoft Office
INTRODUCERE INFORMATII DESPRE MICROSOFT OFFICE Microsoft Office 2000 este un pachet de programe...
Algoritmi Genetici
1 Introducere în calculul evolutiv În general, orice sarcina abstracta care trebuie îndeplinita,...
-
Google
Argument I chose Google because I wanted to write about something relating to the Internet. A...
C, XML, XSL
Exista o probabilitate destul de mare ca după citirea a n articole, toate cu acelaşi subiect, al...