CODEWITHSUNDEEP
javapuzzle
Programmer
Programmer

Reputation: 723

Puzzle to identify shortest route

Today I was going through a problem where we have to identify a shortest distance between a source and destination

There are many nodes say each node is a airport in a city(PSB the image) and count is the number of flights between the cities .Now I have to identify the shortest route between two given cities

Now the way I have thought of is I will take a hashMap which will store source city as key and destination city as value .

Now to identify the shortest route between two given cities what I will do is search the keyset to identify the entry object which contain the source city and search the destination city in the values of the HM like

My HM will be like (ref the image to understand the entries in the hm)

hm.put(h,b);
hm.put(b,c);
hm.put(c,e);
hm.put(b,e);

Now suppose I have been asked to identify the shortest route between h and e

As per my algorithm i will search the keyset of hm for "h" city .

1) I will get <h,b> map entry object Now I will traverse the hm valueSet for "e" city. 2) I will get <c,e> and <b,e> map entry object

Now with the help of the entry.value which is b which I got from Step 1, i will try to associate the key from the entry object I got from Step 2 and thus i will identify that h-b-e is shorter distance compare to h-b-c-e

enter image description here

I not only wants to understand if there is any better solution to the problem but also i want to understand any book or link where I can get such kind of design problems.

Upvotes: 0

Views: 401

Answers (1)

user4668606
user4668606

Reputation:

Have a look at these two algorithms: Djistrak and A*. Your idea is basically quite nice, though it only works for smaller graphs and rather specific conditions.

Upvotes: 2

Related Questions