CHEMINS DANS LES GRAPHES

• Le PCC entre un sommet et tous les autres sommets dans un graphe sans poids

• Le PCC entre un sommet et tous les autres sommets dans un graphe à des poids positifs

• Le PCC entre un sommet et tous les autres sommets dans un graphe pondéré.

• Le PCC entre un sommet et tous les autres sommets dans un graphe orienté et sans cycle

Dist = ∞ for u in GDists = 0P = Ps = s Q = Q.append(s)while Q: z = Q.get_and_delete() for x in Adjz: If Distx > Distz+w(z, x): / ♯ the edge(z, x) is « tense » Distx = Distz+w(z, x) Px = z Q.append(x)Return < P, D >

Generic Shortest Path (G, s)

Le plus court chemin entre 2 sommets

• Données: Un graphe G avec des arêtes (arcs) sans poids et sommet s de G.

• But: Le plus court chemin entre s et les autres sommets du graphe

Complexité: O(V+E)

Dist = ∞ for u in GDists = 0Ps = s Q = Q.append(s)while Q: z = Q.pop() for x in Adjz: If Px == 0: Distx = Distz +1 Px = z Q.append(x) return path(P)

Shortest Path (G, s)

Le plus court chemin: Dijkstra

• Données: Un graphe G avec des arêtes (arcs) à des poids positifs et un sommet s.

• But: Le plus court chemin entre s et les autres sommets du graphe.

Complexité: O(V2+E) // O((V+E)log V) // O(E+Vlog V)

Dist = ∞ for u in GDists=0Ps=s Q = Vwhile Q: z = Q.delete_min() for x in Adjz: Relax(z, x)...Return <P, Dist>

The algorithm : DIJKSTRA(G,s)

Dist = ∞ for u in GDists = 0Ps = s Q = Makeheap(V) (using dist-values as keys)while Q: z = Q.deletemin_key() /♯ extract min operation

for x in Adjz: If Distx > Distz+w(z, x) Q.decrease_key(x) /♯Distx = Distz+w(z, x), Px = z

Dijkstra1 (G.w, s)

M = 0 for u in G Dist = ∞ for u in GDists = 0Ps = s Q.add(s) /♯ altenatively, Q={s} and insert nodes when reached

while Q: z = Q.delete_min() for x in Adjz: If Distx > Distz+w(z, x) Q.decrease_key(x) /♯Distx = Distz+w(z, x), Px = z

If Mx==0: Mx=1 Q.add(x)

Dijkstra2 (altenative) (G,s)

• Opérations: Extract-Min Decrease-Key # ops: V E

• Temps/Op.

• Array: O(V) O(1)• Heap: O(logV) O(logV)• Fibonacci Heap: O(logV) O(1) (amortie)

• Complexité totale en Temps:

• Array: O(V2) • Heap: O((V+E)logV)• Fibonacci Heap: O(E+VlogV)

COMPLEXITE

Le plus court chemin: Bellman-Ford

Données: Un graphe valué G et un sommet s sans cycle négatif.But: Le plus court chemin entre s et les autres sommets du graphe.

Complexité: O(VE)

M = 0 for u in G Dist = ∞ for u in GMs=1Dists=0Q.enqueue(s)Ps=s while Q: z = Q.dequeue() Mz=0 for x in Adjz: If Distx > Distz+w(z, x) Distx = Distz+w(z,x) Px = z if Mx==0: Mx=1 Q.enqueue(x)

Bellman-Ford (G.w,s)

Le chemin le plus court: DAGs

• Données: Un graphe orienté et sans cycle G, et un sommet s de G.

• But: Le plus court chemin entre s et les autres sommets du graphe.

Complexité: O(V+E)

Dist = ∞ for u in GDists =0Ps = s Q = Topological_sort(G)while Q: z = Q.pop() for x in Adjz: If Distx > Distz+w(z, x) Distx = Distz+w(z, x) Px = z

SHORTEST_PATHS_DAGs (G.w, s)

Détection des Cycles négatifs

• Données: Un graphe G et un sommet s.• But: G posséde t-il un cycle négatif?

Complexité: O(VE)

M = 0 for u in G, Dist = ∞ for u in G, Dists=0, a =1, Q.enqueue(s), Q.enqueue(♯)while Q: z = Q.dequeue() if z ==♯: if a < n : Q.enqueue(♯) a+=1 elif Q: PRINT ‘G contains a negative cycle’ break for x in Adjz: If Distx > Distz+w(z, x): Distx = Distz+w(z, x) if Mx ≠ a: Mx = a Q.enqueue(x)G does not contains a negative cycle

NEGATIVE_CYCLE(G.w, s)

Currency conversion. Given currencies and exchange rates, what is best way to convert one ounce of gold to US dollars?

1 oz. Gold → 327.25 US Dollar.1 oz. gold → 208.10 → UKPound → 327.00 US Dollar [ 208.10 x 1.5714 ]1 oz. gold → 455.2 Francs → 304.39 Euros → 327.28 UKPound [ 455.2 x 0.6677 x 1.0752 ]

Currency UKPound Euro JapYen Swiss US Dollar Gold (oz.)

UKPound 1.0000 0.6853 0.005290 0.4569 0.6368 208.100

Euro 1.4599 1.0000 0.007721 0.6677 0.9303 304.028 JapYen 189.050 129.520 1.0000 85.4694 120.400 39346.7

Swiss 2.1904 1.4978 0.011574 1.0000 1.3941 455.200

US Dollar 1.5714 1.0752 0.008309 0.7182 1.0000 327.250

Gold(oz.) 0.004816 0.00329 0.0000255 0.002201 0.003065 1.0000

Shortest paths application: Currency conversion