CODEWITHSUNDEEP
pythonpathroutes
binaryBigInt
binaryBigInt

Reputation: 1704

Python shortest path

I have a list of route-objects which keep the start and the end point of that route:

class route:
    def __init__(self, start, end):
        self.start = start
        self.end = end

routeList = [
    route("Munich", "Cologne"),
    route("Berlin", "Hamburg"),
    ...
    ...
]

As the user enters his start and end point i want to find the shortest combination of routes. I have no idea how i could get this to work. I took a look at the dijkstra's algorithm but it looks like this only works with points and distances and not with routes. I only know that i have to do it recursively but i don't know how. Any ideas?

Edit: For example the user could enter:

"start: Munich"
"end: Berlin"

Of course there must be some matching routes in the list which fulfill this wish (it is just an example)

Upvotes: 0

Views: 635

Answers (2)

markiz
markiz

Reputation: 265

Dijkstra will work just fine.

Every city is a node in a graph, every route between two cities is an edge between two nodes. In general graph edges can have weights (Or distances), but if you don't care about the distance and just want a path with the least amount of routes/edges you can set the weight of every edge to 1.

Upvotes: 1

Nick Bastin
Nick Bastin

Reputation: 31299

NetworkX provides the functionality you're looking for.

You need to format your data in such a way that it builds a sensible graph (I'm not entirely sure from your example whether all your data is pairs, or whether there are more "hops" in some "routes"), and then you can apply any reasonable path finding algorithm.

Upvotes: 1

Related Questions