shortest path

savecancel

After a long manual edit, here is some code that uses the posted code, edits it somehow to have a list of dictionaries, so that "double" / "multiple" keys do not overwrite each other and the last one wins:

L = [
  { "1a" : {"2a" :521916, "22a": 182390, "23a": 144448, "44a": 1199260, "101a": 73200} }
, { "23a": {"24a":200324,"101a": 193980} }
, { "2a" : {"3a" :193980} }
, { "3a" : {"4a" :176900} }
, { "4a" : {"5a" :78080}  }
, { "5a" : {"6a" :599386} }
, { "6a" : {"7a" :633180, "30a":845582} }
, { "7a" : {"8a" :293532} }
, { "8a" : {"9a" :197030, "32a":562420} }
, { "9a" : {"10a":97600} }
, { "10a": {"17a":154940} }
, { "9a" : {"16a":342820} }
, { "16a": {"17a":354898,"18a":164578, "15a":309880,"18a":164578} }
, { "15a": {"14a":592920} }
, { "18a": {"19a":147559} }
, { "19a": {"20a":338550} }
, { "20a": {"21a":190930} }
, { "21a": {"7a" :26230}  }
, { "32a": {"31a":207400} }
, { "11a": {"12a":498980} }
, { "33a": {"34a":378200} }
, { "34a": {"35a":196176} }
, { "30a": {"28a":200080} }
, { "28a": {"29a":390888} }
, { "29a": {"25a":462136} }
, { "25a": {"26a":536800} }
, { "2a" : {"25a":183000} }
, { "26a": {"27a":694790} }
, { "27a": {"28a":747128} }
, { "27a": {"41a":317200} }
, { "41a": {"42a":451400} }
, { "42a": {"12a":85400}  }
, { "41a": {"40a":660020} }
, { "42a": {"44a":500566} }
, { "12a": {"64a":231800} }
, { "64a": {"65a":505568} }
, { "45a": {"46a":581696} }
, { "46a": {"47a":819352} }
, { "47a": {"48a":486292} }
, { "48a": {"49a":466406} }
, { "49a": {"50a":292800} }
, { "50a": {"51a":744200} }
, { "51a": {"52a":256200} }
, { "52a": {"53a":573400} }
, { "52a": {"54a":744200} }
, { "54a": {"55a":195200} }
, { "55a": {"56a":689300} }
, { "55a": {"62a":366000} }
, { "62a": {"63a":793000} }
, { "56a": {"57a":183000} }
, { "57a": {"58a":149084} }
, { "58a": {"59a":390400} }
, { "59a": {"60a":265960} }
, { "60a": {"61a":378810} }
, { "66a": {"67a":504470} }
, { "67a": {"68a":245830} }
, { "68a": {"69a":213500} }
, { "69a": {"70a":256200} }
, { "67a": {"71a":833138} }
, { "71a": {"72a":686860} }
, { "72a": {"73a":732000} }
, { "73a": {"74a":305000} }
, { "74a": {"75a":207400} }
, { "72a": {"76a":479460} }
, { "76a": {"77a":183000} }
, { "77a": {"78a":512400} }
, { "71a": {"84a":131760} }
, { "84a": {"83a":466040} }
, { "83a": {"85a":187880} }
, { "83a": {"82a":453840} }
, { "82a": {"81a":376980} }
, { "81a": {"80a":451400} }
, { "80a": {"79a":368074} }
, { "85a": {"86a":543266} }
, { "86a": {"87a":513742} }
, { "87a": {"88a":699426} }
, { "88a": {"89a":685030} }
, { "89a": {"90a":386130} }
, { "89a": {"91a":451400} }
, { "91a": {"92a":669170} }
, { "92a": {"93a":313784} }
, { "93a": {"94a":12.2}   }
, { "93a": {"95a":548024} }
, { "95a": {"96a":45140}  }
, { "86a": {"97a":319640} }
, { "36a": {"37a":31720}  }
, { "98a": {"99a":488000} }
, { "98a": {"39a":644770} }
, { "39a": {"43a":435906} }
, { "49a": {"57a":399916} }
, { "23a": {"101a":193980}}
, { "101a":{"1a" :73200}  }
, { "2a" : {"25a":183000} }
, { "23b": {"101b":82200} }
, { "101b":{"25b":373800} }
, { "25b": {"3b" :63000}  }
, { "3b" : {"4b" :245400} }
, { "4b" : {"6b" :202800} }
, { "6b" : {"7b" :180000} }
, { "7b" : {"8b" :220800} }
, { "8b" : {"13b":246000} }
, { "23a": {"23b":250000} }
, { "101b":{"101a":250000}}
, { "25b": {"25a":250000} }
, { "3b" : {"3a" :250000} }
, { "4b" : {"4a" :250000} }
, { "6b" : {"6a" :250000} }
, { "7b" : {"7a" :250000} }
, { "8b" : {"8a" :250000} }
, { "13b": {"13a":250000} } ]

dic  = {}    # and we will construct it
keys = []
for mydic in L:
    keys.extend( mydic.keys() )
    keys = list( set( keys ) )
keys.sort()

for key in keys:
    dic[key] = {}
    for mydic in L:
        for mykey in mydic:
            if mykey != key:    continue
            for mykeykey, val in mydic[ mykey ].iteritems():
                dic[key][mykeykey] = val

G = Graph( dic )
# G.plot(edge_labels=True).show()
G.shortest_path("4a", "1a", by_weight=True)

Results and the length of shortest path:

sage: G.shortest_path("4a", "1a", by_weight=True)
['4a', '3a', '2a', '1a']

sage: G.shortest_path_length("4a", "1a", by_weight=True)
892796

sage: # G.shortest_paths("4a",  by_weight=True)    # longer list of shortest paths from "4a"