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 = {}
  ....