CODEWITHSUNDEEP
algorithmgraph
kevin
kevin

Reputation: 309

Find shortest path from A to B through C

I am working on design a algorithm for indoor route planing. I hope brilliant people here could give some advices.

I have a source points A and Destnation point B. To go to B from A, I need to go through a staircase c. There are many staircases c1 c2 c3... in the building.

My current algorithm is to use the staircass with the smellest geometrical distance to the source point. However, this is not always optimal since the nearest staircase may be in the opposite direction of the destination point.

Another approach I tried is to compare the real cost for each staircase(using Dijkstra's algorithm), and choose the the staircase with the minimum cost. This way is granteed to be optimal, but it's too costly. It takes too long for calculation.

I am wondering if there is a way to compromise between them..

Upvotes: 2

Views: 1874

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33499

I suggest you run a Djikstra from each of your 5 staircases and save the results in a database (according to your numbers, this takes only a few seconds and is a one-off cost).

Then for each route you wish to plan, you can test going via each of the 5 staircases. The cost from A->c->B is given by two lookups: one for c->A and one for c->B.

Therefore you can find the optimal route in a total of 10 lookups (2 for each staircase) no matter how many edges are in the database.

Upvotes: 1

Related Questions