Ask Your Question
1

shortest path

asked 2017-12-21 10:05:14 +0100

Astra Be gravatar image

updated 2017-12-22 02:28:17 +0100

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 flag offensive 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']
vdelecroix gravatar imagevdelecroix ( 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.)

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

so how should I write the code?

Astra Be gravatar imageAstra Be ( 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...

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

1 Answer

Sort by ยป oldest newest most voted
0

answered 2017-12-22 16:22:30 +0100

dan_fulea gravatar image

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"
edit flag offensive delete link 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?

Astra Be gravatar imageAstra Be ( 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

Question Tools

1 follower

Stats

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

Seen: 768 times

Last updated: Dec 22 '17