Dijkstra's Algorithm



Dijkstra's algorithm solves the single-source shortest-path problem when all edges have non-negative weights. It is a greedy algorithm and similar to Prim's algorithm. Algorithm starts at the source vertex, s, it grows a tree, T, that ultimately spans all vertices reachable from S. Vertices are added to T in order of distance i.e., first S, then the vertex closest to S, then the next closest, and so on. Following implementation assumes that graph G is represented by adjacency lists.
DIJKSTRA (G, w, s)
1.   INITIALIZE SINGLE-SOURCE (G, s)
2.   S ← { }     // S will ultimately contains vertices of final shortest-path weights from s
3.   Initialize priority queue Q i.e., Q  ←  V[G]
4.   while priority queue Q  is not empty do
5.       u  ←  EXTRACT_MIN(Q)    // Pull out new vertex
6.       S  ←  S È {u}
    // Perform relaxation for each vertex v adjacent to u
7.       for each vertex v in Adj[u] do
8.           Relax (u, v, w)
Dijkstra's algorithm runs in O(|E|lg|V|) time.

Comments

Post a Comment

Popular posts from this blog

Stack vs Heap So far we have seen how to declare basic type variables such as int , double , etc, and complex types such as arrays and structs. The way we have been declaring them so far, with a syntax that is like other languages such as MATLAB, Python, etc, puts these variables on the stack in C. The Stack What is the stack? It's a special region of your computer's memory that stores temporary variables created by each function (including the main() function). The stack is a "FILO" (first in, last out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, it is "pushed" onto the stack. Then every time a function exits, all of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables. The advantage of using the stack to store variable...
Read more

Validate Mobile Number with 10 Digits in ASP.Net

Here is the code for validating textbox for 10 digit mobile number. .ASPX File: <asp:TextBox ID="TextBox1" runat="server"></asp:TextBox><br\>     <asp:RegularExpressionValidator ID="RegularExpressionValidator1" runat="server"        ControlToValidate="TextBox1" ErrorMessage="RegularExpressionValidator"      ValidationExpression="[0-9]{10}"></asp:RegularExpressionValidator>
Read more
What is  Abstraction? Abstraction is another good feature of OOPS. Abstraction means to show only the necessary details to the client of the object . Do you know the inner details of the Monitor of your PC? What happen when you switch ON Monitor? Does this matter to you what is happening inside the Monitor? No Right, Important thing for you is weather Monitor is ON or NOT. When you change the gear of your vehicle are you really concern about the inner details of your vehicle engine? No but what matter to you is that Gear must get changed that’s it!! This is abstraction; show only the details which matter to the user.  Let’s say you have a method "CalculateSalary" in your Employee class, which takes EmployeeId as parameter and returns the salary of the employee for the current month as an integer value. Now if someone wants to use that method. He does not need to care about how Employee object calculates the salary? An only thing he needs to be concern is name...
Read more