Algoritmo del percorso più breve usando i dizionari [Python]

Question

Questa è la mia prima domanda e in realtà la prima volta provo questo, ma leggo le regole delle domande e spero che la mia domanda sia conforme a tutte loro.

Ho un progetto per il mio soggetto algoritmo, ed è quello di progettare un gui per il percorso più breve dijkstra algorthim. Ho scelto di usare python perché è un linguaggio che mi piacerebbe padroneggiare. Ho provato per più di una settimana e sto affrontando problemi fino in fondo. Ma comunque è divertente :)!

ho scelto di rappresentare il mio grafo orientato come un dizionario in questo modo:

g= {'A': {"B": 20, 'D': 80, 'G' :90}, # A can direct to B, D and G 
'B': {'F' : 10}, 
'F':{'C':10,'D':40}, 
'C':{'D':10,'H':20,'F':50}, 
'D':{'G':20}, 
'G':{'A':20}, 
'E':{'G':30,'B':50}, 
'H':None} # H is not directed to anything, but can accessed through C 

così la chiave è il vertice e il valore è il vetrices collegate ei pesi. Questo è un esempio di grafico ma stavo progettando di chiedere all'utente di inserire i propri dettagli del grafico ed esaminare il percorso più breve tra ciascun due nodi [inizio -> fine] Il problema è comunque che non so nemmeno come accedere il dizionario interno in modo che possa lavorare sulle paramteters interiori, e ho provato molti modi, come quei due:

for i in g: 
    counter = 0 
    print g[i[counter]]  # One 
    print g.get(i[counter]) # Two 

ma entrambi mi danno lo stesso risultato che è: (si noti che non posso davvero accedere e riprodurre con i paramters interni)

{"B": 20, 'D': 80, 'G' :90} 
{'F' : 10} 
{'C':10,'D':40} 
{'D':10,'H':20,'F':50} 
{'G':20} 
{'A':20} 
{'G':30,'B':50} 
None 

quindi la mia domanda è, la prego di aiutarmi con il modo di accedere ai dizionari interni in modo da poter iniziare a lavorare su l'algoritmo i tself. Grazie mille in anticipo e grazie per la lettura.

Answer 1

Utilizzando un loop for si scandire le chiavi di un dizionario, e con il tasto, è possibile recuperare il valore associato alla chiave. Se il valore stesso è un dizionario, puoi usare un altro ciclo.

for fromNode in g: 
    neighbors = g[fromNode] 
    for toNode in neighbors: 
     distance = neighbors[toNode] 
     print("%s -> %s (%d)" % (fromNode, toNode, distance)) 

Nota che per far funzionare tutto questo, è necessario utilizzare un dizionario vuoto {} invece di None, quando non ci sono vicini.

Answer 2

Questo in realtà non è così difficile, e dovrebbe essere completo dopo averlo visualizzato. Prendiamo il tuo g. Vogliamo ottenere il peso della connessione 'B' dal nodo 'A':

>>> d = g['A'] 
>>> d 
{"B": 20, 'D': 80, 'G' :90} 
>>> d['B'] 
20 
>>> g['A']['B'] 
20 

Utilizzando g['A'] noi ottiene il valore della chiave nel dizionario g. Possiamo agire direttamente su questo valore facendo riferimento alla chiave 'B'.

Answer 3

Credo che questi darvi alcune idee:

for dict in g: 
    print dict.get("B","") 

for dict in g: 
    print dict.keys() #or dict.values() 

for dict in g: 
    print dict["B"]