Discussion :

[Peter_M31]

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)

[wiztricks]

Salut,

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.

Parce qu'on a définit une valeur par défaut aux paramètres qu'on peut omettre.
(mais comme il s'agit de mutables... c'est "dangereux" et plutôt ici, juste une fioriture pour dire qu'on n'utilise pas de variables globales alors qu'on se repasse le même objet).

- W

[Fifan31]

Bonjour,

La fonction est appelée avec seulement 3 paramètres sur 6 car les 3 derniers ont une valeur par défaut.
Par contre, il vaudrait mieux utiliser 'None' comme valeur par défaut et tester les paramètres dans le corps de la fonction:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
def mafonction(param_obligatoire, param_avec_defaut=None):
  if param_avec_defaut is None:
    param_avec_defaut = {}
  ....