[PDF] [PDF] The Shortest Path Problem The Shortest Path Problem Integer

[PDF] Lecture 18 Solving Shortest Path Problem: Dijkstras Algorithm

23 oct 2009 · Importance: Where it has been used? • Algorithm's general description • Algorithm steps in detail • Example Operations Research Methods 1 

[PDF] Dijkstras Algorithm: Example We want to find the shortest path from

Dijkstra's Algorithm: Example We want to find the shortest path from node 1 to all other nodes using Dijkstra's algorithm Operations Research Methods 11 

[PDF] Dijkstras algorithm revisited: the dynamic programming connexion

It is also popular in operations research It is generally viewed and presented as a greedy algorithm In this paper we attempt to change this perception by 

[PDF] RESEARCH ON THE OPTIMIZATION OF DIJKSTRAS ALGORITHM

algorithm has been obtained, which has reduced the storage space and improved the operational efficiency Keywords: Applications, Directed Graph, Dijkstra's 

[PDF] The Shortest Path Problem

Dijkstra's Shortest Path Algorithm Input: A distance matrix C for a digraph G = (V,E) with n vertices If the edge (i, j) belongs to E the c(i, j) equals the distance from i to j, otherwise c(i, j) equals ∞

[PDF] Anapplication of Dijkstras Algorithm to shortest route - IOSR Journal

Dijkstra (1959) proposed a graph search algorithm that can be used to solve the single-source shortest path problem for any graph that has a non-negative edge  

Research on Optimal Path based on Dijkstra Algorithms

Through the research and optimization of the optimal path problem by various During the operation of Dijkstra algorithm, different paths are repeatedly 

[PDF] The Shortest Path Problem The Shortest Path Problem Integer

Use the Dijkstra algorithm Does that work???? 15 Jesper Larsen Jens Clausen Department of Management Engineering / Operations Research

[PDF] dijkstra algorithm java

[PDF] dijkstra algorithm java explained

[PDF] dijkstra algorithm mit

[PDF] dijkstra algorithm pdf

[PDF] dijkstra algorithm ppt

[PDF] dijkstra algorithm pseudocode

[PDF] dijkstra algorithm python

[PDF] dijkstra algorithm runtime

[PDF] dijkstra algorithm space complexity

[PDF] dijkstra algorithm table

[PDF] dijkstra algorithm time and space complexity

[PDF] dijkstra algorithm time complexity

[PDF] dijkstra algorithm time complexity proof

[PDF] dijkstra algorithm visualization

[PDF] dijkstra pseudocode

1Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

The Shortest Path Problem

Jesper Larsen & Jens Clausen

jla,jc@imm.dtu.dk

Department of Management Engineering

Technical University of Denmark

2Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

The Shortest Path Problem

Given adirectednetworkG= (V,E,w)for

which the underlying undirected graph is connected.Furthermore, asource vertexris given.Objective:Find for eachv?Va shortest directed path fromrtov(if such one exists).Letndenote the number of nodes andmthe number of edges inG.

3Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Integer Programming Formulation

Supposeris the source vertex. Look at the

numberof paths leaving a vertex vs. the numberof paths entering a vertex.

Forr n-1paths have to leaver.For any other vertex, the number of pathsentering the vertex must be exactly 1 largerthan the number of paths leaving the vertex.

Letxedenote thenumberof paths using each

edgee?E.

4Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Mathematical ModelThis gives the following mathematical model: min e?Ew exe s.t. i?Vx ir-? i?Vx ri=-(n-1) i?Vx ij-? i?Vx ji= 1j? {2,...,n} x e? Z+e?E

5Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Feasible potentials

Consider ann-vectory=y1,...,yn.Ifysatisfies thatyr= 0and ?(i,j)?E:yi+wij≥yj thenyis called afeasiblepotential.

6Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Feasible potentials II

IfPis a path fromrtov?V, then ifyis a

feasible potential,wP≥yv: w

P=?ki=1wei

≥?ki=1(yvi-yvi-1) =yvk-yv0 =yv

7Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Basic algorithmic idea

Start with the potential withyr= 0and

y

i=∞, i?V\ {r}Check for each edge if the potential is feasibleIf YES - Stop - the potentials identify shortestpathsIf an edge(i,j)violates the feasibility condition,

updateyj- this is sometimes called "correct (i,j)" or "relax(i,j)"

8Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Ford's Shortest Path Algorithm

yr←0,yi← ∞for all otheri1 p r←0,pi←Nilfor all otheri2 whilean edge exists(i,j)?Esuch that3 y j> yi+wijdo yj←yi+wij4 p j←i5

9Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Problem with Ford's Algorithm

Complexity !Beware ofnegative length circuits

- these may lead to infinite computation.Solution:Use the same sequence for the edges in each iteration.

10Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Bellman-Ford's Shortest Path Algorithm

yr←0;yi← ∞for all otheri1 p r←0;pi←Nilfor all otheri2 k←03 whilek < nand¬(yfeasible)do4 k←k+ 15 for(i,j)?Edo/* correct(i,j)*/6 ifyj> yi+wijthen7 yj←yi+wij8 p j←i9

11Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Complexity of Bellman-Ford's AlgorithmA worst-case time complexity analysis leads to thefollowing conclusions:

Initialization:O(n).Outer loop:(n-1)times.In the loop: each edge is considered one time -O(m).All in all:O(nm).

12Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Bellman-Ford's Algorithm

Proof is based on induction.The induction hypothesis is: After iterationkof the main loop,yicontains the length of any shortest path withat mostkedges from 1 toi for anyi?V.For the base casek= 0the induction hypothesis is trivially fulfilled. (yr= 0 =shortest path fromrtor).

13Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Bellman-Ford's Algorithm II

For the inductive step, we assume thatyvi-1=

shortest path fromrtovi-1after the(i-1)'st pass. Then(vi-1,vi)is relaxed in thei'th iteration. Soyvi= shortest path fromrtovi.If all distances are non-negative, a shortest path containing at most(n-1)edges exists for eachv?V. If negative edge lengths are present, the algorithm still works. If anegative length circuitexists, this can be discovered by an extra iteration in the main loop. If at least on y ichanges, there is a negative length circuit.

14Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Introduction to Dijkstra's Algorithm

If we assume all edge weights are non-negative

we can derive a more efficient algorithm.A new algorithm for a general graph couldtherefore be: Find the most negative edgeweightweand add|we|to all edge weights. Now

allwf≥0for allf?E. Use the Dijkstra algorithm. Does that work????

15Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Dijkstra's Algorithm for Shortest Path

S← {r},T← ∅1

p r←0,yr←02 p i←Nil,yi← ∞for all otheri3 whileS?=∅do4 select ai?Sminimizingyi5 for{j?V:j??T?(i,j)?E}do6 ifyj> yi+wijthen7 yj←yi+wij,pj←i8

S←S? {j}9

S←S\ {i},T←T? {i}10

16Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Example

3 4 7 6 25
31
51
1 31
4 1 31
711

17Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Complexity of Dijkstras Algorithm

The only difference to Prim's algorithm for

Minimum Spanning Trees is the update step in

the inner loop, and this step takes - like in the MST algorithm -O(1).Hence the complexity of the algorithm isO(n2) if a list representation of theyvector is used, and a complexity ofO(mlogn)can be obtained if theheapdata structure is used for the representation ofyvector.

18Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Dijkstras Algorithm

This proof is made by induction:Suppose that before an iteration of thewhile loop it holds that

1. for each vertexu?T, the shortest path from

rtouhas been found and is of lengthyu, and

2. for each vertexu??T,yuis the shortest path

from fromrtouwith all vertices exceptu belonging toT.This is obviously true initially.

19Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Dijkstras Algorithm II

Letvbe the element with leastyvalue picked

initially in the inner loop of iterationk.yvis the length of a pathQfromrtovpassing only through vertices inT.Suppose that this is not the shortest path fromr tov- then another pathRfromrtovis shorter.

20Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Dijkstras Algorithm III

RQ v wur

21Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Dijkstras Algorithm IV

Look atR:Rstarts inr, which is inT. Sincev

is not inT,Rhas an edge from a vertex inPto a vertex not inT.Let(u,w)be the first edge of this type.wis a candidate for vertex choice in the current

iteration, wherevwas picked. Henceyw≥yv.If all edge lengths are non-negative, the lengthof the part ofRfromwtovis non-negative, and

hence the total length ofRis at least the length of the pathQ.

22Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Dijkstras Algorithm V

This is a contradiction - henceQis a shortest

path fromrtov.Furthermore, the update step in the inner loopensures that after the current iteration it againholds forunot inP(which is now the "old"P

augmented withv) thatyuis the shortest path from fromrtouwith all vertices exceptu belonging toP.

23Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Floyd-Warshall's all-to-all Algorithm

yij←wij,pij←ifor all(i,j)withwij?=∞,1 p ij←0otherwise. fork←1tondo2 fori←1to ndo3 forj←1tondo4 ifi?=k?j?=k?yij> yik+ykjthen5 yij←yik+ykj6 p ij←pkj7

24Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Complexity of Floyd-Warshall's Algorithm

In addition to the initialisation, which takes

O(n2), the algorithm has three nested loops

each of which is performedntimes.The overall complexity is henceO(n3).

25Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Floyd-Warshall's Algorithm

This proof is made by induction:Suppose that prior to iterationkit holds that for i,j?v yijcontains length of the shortest path

QfromitojinGcontaining only vertices in the

vertex set{1,...,k-1}, and thatpijcontains the immediate predecesor ofjonQ.This is obviously true after the initialisation.

26Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Floyd-Warshall's Algorithm II

In iterationk, the length ofQis compared to the

length of a pathRcomposed of two subpaths, R1andR2.R1is a path fromitokpath with "intermediate vertices" only in{1,...,k-1}, andR2is a path fromktojpath with "intermediate vertices" only in{1,...,k-1}. The shorter of these two is chosen.

27Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Floyd-Warshall's Algorithm III

contains only vertices from {1,..., k-1}QR2 R1 p[i,j] j p[k,j]k i

28Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

Correctness of Floyd-Warshall's Algorithm III

The shortest path fromitojinGcontaining

only vertices in the vertex set{1,...,k}either

1. does not containk- and hence is the one

found in iterationk-1, or

2. containsk- and then can be decomposed

into a path fromitokfollowed by a path fromktoj, each of which has been found in iterationk-1.Hence the update ensures the correctness ofthe induction hypothesis after iterationk.

29Jesper Larsen & Jens ClausenDepartment of Management Engineering / Operations Research

3 4 7 6 25
31
51
1 31
4 1 31
711
quotesdbs_dbs14.pdfusesText_20