Dijkstra algorithm

50 %
50 %
Information about Dijkstra algorithm

Published on March 9, 2014

Author: gsp1294

Source: slideshare.net

Dijkstra Algorithm: Finding shortest paths in order Find shortest paths from source s to all other destinations w' z w s x w" z' x'

Djikstra's algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination.

• Suppose we want to find a shortest path from a given node a to other nodes in a network (one-to-all shortest path problem) • It finds the shortest path from a given node a to all other nodes in the network • Node a is called a starting node or an initial node

we will find the shortest path from a to e.

Dijkstra's algorithm keeps two sets of vertices: Set P : The set of vertices whose shortest paths from the source have already been determined and Set T : The remaining vertices.

So here initially P = {} i.e. Empty T = {a,b,c,d,f}

Step 1: Label a with 0 and all others with . Labels are shortest paths from a to vertices. So we have P={a} T = { b, c, d, e} L(a) = 0 L(b) =  L(c) =  L(d) =  L(e) = 

Step 2: • Nodes b, c, and d can be reached from the current node a • Therefore by using L( i ) = min { L( n ), L( j ) + w( i , j ) } Where L(i) = label we are Updating. L(j) = Current Label Update distance values for these nodes

So we get L ( b ) = min { L( b ) , L( a ) + W ( a , b ) } = min {  , 0 + 9 } = min { , 9 } Selecting the minimum we get L (b) = 9 Smilarly calculating for L(c) and L(d) we get L(c) = min { , 19} = 19 L(d) = min { , 25} = 25

• Now, among the nodes b, c, and d, node b has the smallest distance value. • So the status label of node b changes to permanent, while the status of c and d remains temporary

Step 3: • P = { a, b} • T = { c, d, e} • Node b becomes the current node Operation • Nodes c, and e can be reached from the current node b. So, updating values for c, d, e We get • L (c)= min { 19 , 9+16 } = min { 19 , 25} = 19 • Similarly ( e ) = 45 • Now label c has the smallest value. Therefore it changes to permanent.

Step 4: • P = {a , b, c} • T = { d, e } • Updating labels for d and e, we get • L (d) = 24 and L (e) = 50

• • • • Step 5 : P ={ a,b,c,d } , T = {e} Updating label e , we get L (e) = 45 So 45 is the shortest value which can be travelled to reach node e.

Applications Telephone Network The vertices represents switching station, the edges represents the transmission line, and the weight of edges represents the BW. Flight Agenda To determine the earliest arrival time for the destination given an origin airport and start time.

Add a comment

Related presentations

Related pages

Dijkstra-Algorithmus – Wikipedia

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der ...
Read more

Dijkstra's algorithm - Wikipedia, the free encyclopedia

Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest-distance, calculates the distance through it ...
Read more

Edsger W. Dijkstra – Wikipedia

Leben. Edsger Dijkstra wurde als Sohn eines Chemikers und einer Mathematikerin geboren. Nach dem Besuch des Gymnasiums Erasmianum in Rotterdam studierte er ...
Read more

Dijkstra-Algorithmus - Orklaert- Operations Research ...

Dijkstra-Algorithmus. Der Dijkstra-Algorithmus oder auch Algorithmus von Dijkstra ist ein Algorithmus der nach seinem Erfinder Edsger Wybe Dijkstra benannt ...
Read more

Dijkstra Algorithm - CodeProject - CodeProject - For those ...

Shortest path (Dijkstra's Algorithm); Author: lgciprian; Updated: 24 Dec 2003; Section: Algorithms & Recipes; Chapter: General Programming; Updated: 24 Dec ...
Read more

Dijsktra's algorithm - GeeksforGeeks | A computer science ...

Given a graph and a source vertex in graph, find shortest paths from source to all vertices in the given graph. Dijkstra’s algorithm is very similar to ...
Read more

DIJKSTRA’S ALGORITHM - Massachusetts Institute of Technology

Dijkstra’s Algorithm ! Solution to the single-source shortest path problem in graph theory ! Both directed and undirected graphs ! All edges must have ...
Read more

Dijkstra's shortest path algorithm in Java - Tutorial

Dijkstra's Shortest Path Algorithm in Java Dijkstra's Algorithms describes how to find the shortest path from one node to another node in a directed ...
Read more

Algorithmus von Dijkstra – GISWiki - Geoinformatik ...

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem ...
Read more

Der Dijkstra-Algorithmus - YouTube

Dijkstra-Algorithmus Tutorial [german / HD] - Duration: 8:19. ... Dijkstra 's Algorithm for Shortest Route Path - Duration: 10:55.
Read more