shortest path or route algorithm [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

There are pre-defined routes.

Route1 [Edirne (1)-Kırklareli (2)-Istanbul (3)]
Route2 [Istanbul (3) - Sakarya (4) - Zonguldak (5)]
Route3 [Istanbul (3) - Kutahya (6) - Afyon(7)]
Route4 [Afyon(7) - Isparta (8) - Anatlya(9)]

Every route has a vehicle which traverses on it.

For example, if some goods will be sent from Edirne(1) to Antalya(9) Route1-Route3-Route4 must be chosen.

If the case is Zonguldak to Edirne Route1-Route2 must be choosen.

etc..

Shortest path algorithms based on distances between steps and find the "shortest path" not route. Because my locations are in routes, shortest path algorithms are not the correct method for me for this situation. Any ideas on how to solve this problem, || Does anyone have a suggestion?

Answer 1

Shortest Path still applies; you just need to change your thinking. Rather than include edges between every city on your route, translate Route 1 into Vertices at Edirne and Istanbul and a single edge between them (weighted to your route length). Ignore the fact that it goes through Kirklareli.

Do the same for your other routes and you'll have something like

Edirne--1--Istanbul--2--Zonguldak
               |
               3 
               |
             Afyon--4--Anatlya

Then you can apply a shortest path and you'll find that Edirne to Anatlya is 1-3-4, which you then translate back into the full route (Edirne - Kırklareli - Istanbul - Isparta - Anatlya)