Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | |||
jour_tp_chemin:dijjstra [2018/11/07 21:35] – pprea | jour_tp_chemin:dijjstra [2018/11/16 14:43] (Version actuelle) – pprea | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | <code python> | ||
+ | import math | ||
+ | INFINI = math.inf | ||
+ | NEIGHBOURS = " | ||
+ | |||
+ | def dijkstra(graph, | ||
+ | distances = {} | ||
+ | ancestors = {} | ||
+ | unknown = {} | ||
+ | path = [] | ||
+ | finish = False | ||
+ | for city in graph: | ||
+ | unknown[city] = True | ||
+ | ancestors[city] = origin | ||
+ | if city in graph[origin][NEIGHBOURS]: | ||
+ | distances[city] = graph[origin][NEIGHBOURS][city] | ||
+ | else: | ||
+ | distances[city] = INFINI | ||
+ | distances[origin] = 0 | ||
+ | unknown[origin] = False | ||
+ | new_city = origin | ||
+ | while not finish: | ||
+ | minimum = INFINI | ||
+ | for city in graph: | ||
+ | if unknown[city] and distances[city] < minimum: | ||
+ | new_city = city | ||
+ | minimum = distances[city] | ||
+ | if minimum == INFINI: | ||
+ | finish = True | ||
+ | unknown[new_city] = False | ||
+ | for town in graph[new_city][NEIGHBOURS]: | ||
+ | if distances[new_city] + graph[new_city][NEIGHBOURS][town] < distances[town]: | ||
+ | distances[town] = distances[new_city] + graph[new_city][NEIGHBOURS][town] | ||
+ | ancestors[town] = new_city | ||
+ | if (destination is not None) and (distances[destination] != INFINI): | ||
+ | city = destination | ||
+ | while city != origin: | ||
+ | path.append(city) | ||
+ | city = ancestors[city] | ||
+ | path.append(origin) | ||
+ | path.reverse() | ||
+ | return [distances, path] | ||
+ | | ||
+ | </ |