Ask Your Question

# shortest path

Hi, I wanna find the best route by minimizing the cost form 4a to 1a, I write this code in Cocalc

G = Graph({"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}}) G.plot(edge_labels=True).show() # long time G.shortest_path("4a", "1a", by_weight=True)

<change> I mean I wrote G.shortest_path("4a", "1a", by_weight=True) instead of G.shortest_path("3a", "2a", by_weight=True)

but it gives me 4a,5a,6a,30a, 28a, 29a, 25a, 2a,1a (which is not the best route) because i try to manually calculate and there's a better route which is 4a, 3a, 2a, 1a

so, why this g.shortest_path doesn't give me the shortest one?

n btw what's the command to print/show the total cost of the chosen shortest path?

Thanks, Astra Ps. I'm new to sagemath

edit retag close merge delete

## Comments

(3a, 2a) is not an edge of your graph and hence can not be part of a (shortest) path

sage: G.neighbors("2a")
['1a', '25a']
sage: G.neighbors("3a")
['3b', '4a']

( 2017-12-21 17:40:06 +0100 )edit

G is constructed as Graph(dic) where

dic = {"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}, # # # ???


and so on, but keys repeat themselves . Not only "9a" above! Finally for instance:

sage: dic[ '2a' ]
{'25a': 183000}


Please use markdown for the code. (Press Control+K "on" marked code.)

( 2017-12-21 17:43:04 +0100 )edit

so how should I write the code?

( 2017-12-22 03:25:25 +0100 )edit

We still do not know what dictionary with values dictionaries is the needed one. But the last mention of a key wins, e.g.

sage: dic = { 'a': [32764, 7365], 'a': 'nothing', 'a':0 }
sage: print dic
{'a': 0}


How was the input generated?

Note: If there is a much simpler situation that also produces the "error", it is better to post the simpler situation. In this comment is no place to use all the dictionary. I will try to give an answer using the whole dictionary...

( 2017-12-22 13:49:27 +0100 )edit

## 1 Answer

Sort by ยป oldest newest most voted

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"

more

## Comments

This is really helpful, just a little bit more....I don't really understand the 'construct part', because it seems there's no different when I run the code with or without the 'construct part' and in Cocalc can we have a better visualization for the graph?

( 2017-12-23 05:39:20 +0100 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2017-12-21 10:01:47 +0100

Seen: 525 times

Last updated: Dec 22 '17