Bonjour,
Je suis nouveau sur le forum, et j'ai une question à laquelle je n'ai pas trouvé de réponse. Je m'intéresse à un programme qui implémente l'algorithme de Dijsktra, que j'aimerais comprendre, notamment dans la façon dont celui-ci est appelé :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
def dijkstra(graph,position,dest,visited=[],distances={},predecessors={}):
et l'appel récursif suivant:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
dijkstra(graph,min(unvisited, key=unvisited.get),dest,visited,distances,predecessors)
Ma question est comment est-il possible que l'appel à cette fonction fonctionne correctement avec le passage de 3 paramètres (graph, position,dest), alors que 6 paramètres sont définis pour la fonction.
Merci d'avance.

Peter_M31.

Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed May  8 13:41:17 2019
"""
 
def dijkstra(graph,position,dest,visited=[],distances={},predecessors={}):
 
    print("graph :",graph)
 
    # On verifie si les 2 points sont dans notre réseau
    if position not in graph:
        print('Le point de départ n\'existe pas.')
 
    if dest not in graph:
        print('Le point d\'arrivée n\'existe pas.')    
 
    if position != dest:
        # On commence en mettant le point de départ à 0
        if not visited: 
            distances[position]=0
        # Puis nous visitons les points voisins pour calculer leurs distances 
        for neighbor in graph[position]:
            if neighbor not in visited:
                new_distance = distances[position] + graph[position][neighbor]
                if new_distance < distances.get(neighbor,float('inf')):
                    distances[neighbor] = new_distance
                    predecessors[neighbor] = position
        # On marque les points voisins comme étant visités
        visited.append(position)
        # Maintenant que les points voisins sont visités, on choisit le prochain point avec le poids le plus bas.
        unvisited={}   
 
        for p in graph:
            if p not in visited:
                unvisited[p] = distances.get(p,float('inf'))        
        dijkstra(graph,min(unvisited, key=unvisited.get),dest,visited,distances,predecessors)
    else :
        # Maintenant que tous les points dans le réseau sont visités, on obtient le chemin 
        path=[]
        pred=dest
        while pred != None:
            path.append(pred)
            pred=predecessors.get(pred,None)
        print('Le chemin le plus court (reste a mettre a l\'envers) : '+str(path)+" avec une distance de "+str(distances[dest]))
 
 
 
start = input('Point de départ : ').lower()
dest = input ('Point d\'arrivé : ').lower()
# Le réseau est donné sous la forme de "graph"
graph = {
        "a":{"b":2,"c":5},
        "b":{"e":2},
        "c":{"e":1,"b":2},
        "d":{"c":4,"b":1},
        "e":{"f":2,"d":4},
        "f":{"d":1}
        }
dijkstra(graph,start,dest)