1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| from math import inf
# nombre de noeuds dans le graphe
n = 7+1
# graph contient les liens (sommet, sommet_adjacent, distance_entre_les_deux)
graph = [
(0, 0, 0), # un faux sommet isolé pour commencer à 1...
(1, 2, 1),
(1, 3, 1),
(1, 4, 1),
(2, 1, 1),
(2, 7, 1),
(2, 4, 2),
(2, 3, 2),
(2, 6, 2),
(2, 5, 3),
(3, 1, 1),
(3, 6, 1),
(3, 5, 1),
(3, 4, 2),
(3, 7, 2),
(3, 2, 2),
(4, 1, 1),
(4, 5, 1),
(4, 3, 2),
(4, 2, 2),
(4, 7, 3),
(4, 6, 3),
]
# nombre d'arêtes
m = len(graph)
def BellmanFord(src):
# On initialise la distance du sommet source au sommet source à 0 et du sommet source aux autres sommets à l'infini
dist = [float("inf") for i in range(n)]
dist[src] = 0
# Relax all edges | V | - 1 times. A simple shortest path from src to any other vertex can have at-most |V| - 1 edges
for i in range(n-1):
# Update dist value and parent index of the adjacent vertices of the picked vertex. Consider only those vertices which are still in queue.
for u, v, w in graph:
if dist[u] != float("inf") and dist[u]+w < dist[v]:
dist[v] = dist[u]+w
# Etape 3 : on gère les arêtes de poids négatif et les cycles.
cycle = 0
for u, v, w in graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
print("Le graphe contient un cycle de poids négatif")
cycle = 1
break
if cycle == 0:
print('Distance depuis le sommet origine',src)
print("Sommet \t Distance depuis l'origine")
for i in range(len(dist)):
print(i,'\t',dist[i])
BellmanFord(1)
|
