Dijkstra

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Dijkstra’s Algorithm for Finding Shortest Paths:

Dijkstra’s Algorithm for Finding Shortest Paths Irena Pevac

Shortest Paths:

Shortest Paths Def: The distance along the path is the sum of the labels of that path. Def: The minimum distance from node u to node v is the minimum of the distance on any path from u to v. Dijkstra algorithm gives efficient way to find the minimum distance from the source node to all the nodes of the graph. Graph can be either directed or undirected.

Settled and Unsettled Nodes:

Settled and Unsettled Nodes We discover the minimum distance from the source to other nodes in the order of those distances. We will call settled nodes those nodes for which we know their minimum distance. The set of settled nodes always includes source. For unsettled nodes v, we record the length of the shortest path that starts at the source, travels only through settled nodes, and at last step jumps out of the settled region to v.

Dijkstra’s Algorithm for Finding Shortest Paths:

Dijkstra’s Algorithm for Finding Shortest Paths Initially only the source node s is settled. Its distance to the source dist(s)=0. If there is an arc from s to u dist(u) is the label of that arc. If there is no arc from s to u, the dist(u)= . Assume that some nodes are settled. We find the node v that is unsettled. We settle v by Make dist(v) to be the min distance from s to v. Adjust the value of dist(u) for all nodes u that remain unsettled, to account for the fact that v is now settled.

Example :

Example

Start at A:

Start at A Node Step1 Step2 Step3 Step4 Step5 A 0* 0* 0* 0* 0* B 3 3* 3* 3* 3* C  7 7 7* 7* D 7 5 5* 5* 5* E   9 9 9*

Dijkstra(G,s):

Dijkstra(G,s) for every vertex v in V dv =  Insert (Q, v, dv) // initialize vertex priority in PQ Dist(s)=0 Decrease(Q,s,dist(s)) For i = 0 to |V|-1 u*=DeleteMin(Q) V T =V T U {u*} for every vertex u in V-V T that is adjacent to u* if (dist(u*) +label(u*,u) < dist(u)) dist(u)= dist(u*)+ label(u*,u) u is settled. Decrease(Q,u,dist(u))

Time efficiency for Dijkstra’s Algorithm:

Time efficiency for Dijkstra’s Algorithm Let G=(V,E) |V|=n |E|=m Let graph be represented with weight adjacency matrix, and priority queue be implemented as an unordered array. Time is  (n 2 ). Let graph be represented with weight adjacency lists, and priority queue be implemented as a min heap. Time is  ( m logn).