Dijkstra algorithm

43 %
57 %
Information about Dijkstra algorithm
Education

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.

 User name: Comment:

Related presentations

1122_LED_GroepD_Presentatie

November 19, 2018

1122_Stromen_en_mengen_GroepA_Presentatie

November 19, 2018

7 клас 10 урок Практична робо...

November 19, 2018

1122_Stromen&Mengen_GroepD_Presentatie

November 19, 2018

1122_Helikopter_GroepB_Presentatie2

November 19, 2018

HPE6-A47 Practice Questions Answers

November 16, 2018

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...