import math import argparse import sys # # Données de graph.h directement intégrées dans le code # NB_NODES = 5 # NB_LINKS = 7 # LINKS = [ # [2,0,1], # [0,1,2], # [0,3,3], # [0,4,1], # [1,2,-1], # [3,1,-2], # [3,4,5] # ] def get_file_infos(links): """ Récupère les informations basiques du graphe : le nombre de noeuds et de liens. """ nb_nodes = max(max(link[:2]) for link in links) + 1 nb_edges = len(links) return nb_nodes, nb_edges def bellman_ford(links, s, nb_nodes, verbose): """ Exécute l'algorithme de Bellman-Ford avec comme noeud source `s`. Retourne un tableau de distances pour atteindre chaque noeud depuis `s`, ainsi que le chemin pour atteindre ces noeuds (tableau de précédence). Si le noeud est isolé ou qu'un cycle négatif est trouvé, retourne une distance infinie pour chaque autre noeud, et une distance de 0 pour `s`. """ # Initialisation. dist = [math.inf] * nb_nodes dist[s] = 0 # Le noeud source est à distance 0 de lui-meme. path = [-1] * nb_nodes # Iteration de Bellman-Ford. for _ in range(nb_nodes-1): for j in range(len(links)): node_from, node_to, cost = links[j][0], links[j][1], links[j][2] if (dist[node_from] != math.inf and dist[node_to] > dist[node_from] + cost): dist[node_to] = dist[node_from] + cost path[node_to] = node_from # Detection de cycle negatif. for j in range(len(links)): node_from, node_to, cost = links[j][0], links[j][1], links[j][2] if (dist[node_from] != math.inf and dist[node_to] > dist[node_from] + cost): if verbose: print("Cycle négatif détecté") dist = [math.inf] * nb_nodes dist[s] = 0 path = [-1] * nb_nodes return dist, path def get_path(dest, path, source): """ Retourne une liste contenant le chemin de `source` vers `dest` en utilisant le tableau de précédence `path`. """ r = [dest] i = dest while i != source: r.insert(0, path[i]) i = path[i] return r def get_max(dist, s): """ Retourne l'indice du noeud dont il existe un chemin de `s` vers ce noeud et le cout de ce chemin est le plus élevé parmis tous les noeuds ayant un chemin depuis `s`. """ max_cost = -math.inf max_node = s for node_idx in range(len(dist)): if node_idx != s and dist[node_idx] != math.inf and dist[node_idx] >= max_cost: max_cost = dist[node_idx] max_node = node_idx if max_cost == -math.inf: if dist[s] != math.inf and dist[s] >= max_cost: max_cost = dist[s] return max_cost, max_node def read_graph(): """ Récupère le graphe directement à partir des données définies dans le code. """ global LINKS, NB_NODES nb_nodes, nb_edges = get_file_infos(LINKS) return LINKS, nb_nodes if __name__ == "__main__": parser = argparse.ArgumentParser( description="LEPL1503 - Algorithme de plus court chemin") parser.add_argument( "input_file", help="chemin vers le fichier d'instance representant le graphe a traiter.") parser.add_argument("-f", help="chemin vers le fichier qui contiendra le resultat de programme, au format specifie dans l'enonce. Defaut : stdout.", type=argparse.FileType("wb"), default=sys.stdout) parser.add_argument( "-v", help="autorise les messages de debug. Si ce n'est pas active, aucun message de ce type ne peut etre affiche, excepte les messages d'erreur en cas d'echec. Defaut : False.", action="store_true") args = parser.parse_args() verbose = args.v output_fd = args.f nb_nodes = None nb_edges = None if verbose: # Exemple de message que vous pouvez ecrire si le mode verbose est actif. print(args, file=sys.stderr) graph, nb_nodes = read_graph() if output_fd == sys.stdout or output_fd == sys.stderr: print("Nombre de noeuds: " + str(nb_nodes)) else: output_fd.write(nb_nodes.to_bytes(4, "big")) for source in range(nb_nodes): dist, path = bellman_ford(graph, source, verbose) # Ces messages ne sont pas des messages de debug. # Ils peuvent donc etre affiches (uniquement si la sortie choisie est stdout ou stderr) # meme si le mode verbose n'est pas actif. dist, path = bellman_ford(graph, source, verbose) for i in range(nb_nodes): print(f"Distance to node {i} : {dist[i]}") print(f"Path to node {i} : {path[i]}")