Dijkstra's Moore Algorithm
Uploaded by
ScribdTranslationsDijkstra's Moore Algorithm
Uploaded by
ScribdTranslationsTHE SHORTEST PATH PROBLEM
Pathfinding problems (route, journey, or path) in graphs (in particular the
search for a shortest path) are among the oldest problems in the theory of
graphs and the most important by their applications.
I. DEFINITION :
Let G = (X, U) be a weighted graph; we associate with each edge u=(i, j) a length l(u) or l.ij.
The Problem of the shortest path between i and j is to find a path μ(i, j) from i to j such that:
l(μ) = ∑l(u) where u∈ be minimal.
Interpretation of (μ): transportation cost, construction expense, necessary travel time...
II. PRINCIPLE OF OPTIMALITY:
The principle of optimality states that the sub-paths of the shortest paths are optimal.
shortest paths. If the shortest path PABFrom A to B passes through node C, then the portion PACis a
shortest path from A to C.
Principle of shortest path search algorithms:
- A distance d(i) is associated with the vertex i.
- At the end of the algorithm, this distance represents the length of the shortest path from the origin.
at the summit i.
III. FROM ONE SUMMIT TO ALL OTHERS:
This problem is also called the single-source shortest path problem.
If there is a negative length circuit (absorbing circuit) in the graph, the search for a maximum
the path from the origin to the peak in question is irrelevant. Indeed, one can use the circuit a
infinity of times (leading to the perpetual decrease of the length of the path).
DIJKSTRA'S ALGORITHM
Dijkstra's algorithm is designed to solve the shortest path problem from a source to
all other vertices in a weighted directed graph with positive real numbers.
Notation :
Yes and∈ So X:
- Γ(i) : set of successors of i
- Γ-1set of predecessors of i
- PCC(i): length of the shortest path from a source vertex s to i
- X : set of vertices in the graph
- S : a set of unvisited (unmarked) vertices
Algorithm:
Etape 1 : Initialisation
Choose the origin vertex s
S = X - {s}
PCC(s) = 0
( ), i ∈ Γ(s)
PCC(i)={
∞
Step 2:
Select j∈ Ssuch that: PCC(j) = min (PPC(i)) where iis in S
Make S = S - {j}
If S = {} then STOP
Otherwise go to step 3
Step 3 :
For all i∈ Γ(j)Intersection S
Make PCC(i) = min (PCC(i); PCC(j) + l(j, i))
Return to step 2
Application :
j=s=A
S = {B, C, D, E, F, G}
PCC(A) = 0
PCC(B) = 2
PCC(C) = 7
PCC(D) = ∞
PCC(E) = ∞
PCC(F) = ∞
PCC(G) = ∞
j=B
S = S–{B} = {C, D, E, F, G}
Γ(B){C, D}
Gamma of B∩S = {C, D}
PCC(C) = min (PCC(C), PCC(B) + l(B, C)) = min (7, 2 + 5) = 7
PCC(D) = min (PCC(D), PCC(B) + l(B, D)) = min (∞(2 + 3) = 5
j=D
S = S - {D} = {C, E, F, G}
Γ(D){C, E, F}
Γ(D)∩S = {C, E, F}
PCC(C) = min (PCC(C), PCC(D) + l(D, C)) = min (7, 5 + 1) = 6
PCC(E) = min (PCC(E), PCC(D) + l(D, E)) = min (∞(5 + 6) = 11
PCC(F) = min (PCC(F), PCC(D) + l(D, F)) = min (∞(5 + 7) = 12
j=C
S = S - {C} = {E, F, G}
Γ(C){E, G}
Γ(C)∩S = {E, G}
PCC(E) = min (PCC(E), PCC(C) + l(C, E)) = min (11, 6 + 5) = 11
PCC(G) = min (PCC(G), PCC(C) + l(C, G)) = min (∞(6 + 2) = 8
j=G
S = S - {G} = {E, F}
Γ(G){E, F}
Γ(G)∩S = {E, F}
PCC(E) = min (PCC(E), PCC(G) + l(G, E)) = min (11, 8 + 2) = 10
PCC(F) = min (PCC(F), PCC(G) + l(G, F)) = min (12, 8 + 4) = 12
j=E
S = S - {E} = {F}
Gamma(E)= {F}
Gamma(E)∩S = {F}
PCC(F) = min (PCC(F), PCC(E) + l(E, F)) = min (12, 10 + 1) = 11
j=F
S = S - {F} = {} => STOP
j\i A B C D E F G
A 0 2 7 ∞ ∞ ∞ ∞
B 0 2 7 5 ∞ ∞ ∞
D 0 2 6 5 11 12 ∞
C 0 2 6 5 11 12 8
G 0 2 6 5 10 12 8
E 0 2 6 5 10 11 8
