NeverOnTimeSdnBhd
commented
3 years ago Hi
Interesting question, I am glad that someone starts exploring other searching algorithms for this assignment Dijkstra's algorithm requires a heuristic value for searching, so properly define the heuristic value is very important. The way you define the heuristic value is not suitable in our problem context and that's why you didn't get an expected result.
Also, to be honest I never think about how to adapt Dijkstra's algorithm to this kind of problem before so I can't answer you directly now but I believe most of the searching algorithms can be adapted to your own need. If you can think of a way to make use of Dijkstra's algorithm then it will be very good as it indicates great problem solving skills.
When I am free and if I can think of how to adapt it then maybe I will share here with you.
Then regarding this
So is it suitable for me to use Dijkstra's algorithm as my extra algorithm or should I try another algorithm to solve this problem? I would say not so suitable in the first place, but as what I mentioned earlier, almost all searching algorithm can be adapted.
Another small hint: Besides thinking it as a searching problem, try to think from another perspective. This problem can be treated as a combinatorial problem also (aka. finding the best combination of routes).
Hello NeverOnTimeSdnBhd
Currently I'm trying to implement Dijkstra's algorithm to find the shortest path for each customers. Dijkstra's algorithm is an informed search which will find the path with the lowest cost for a target vertex. In my case, the source vertex is Depot and the target vertices are Customers.
Below is the neighbors for each vertex in my program
The distance of each neighbors from a vertex
Below are the early results of my Dijkstra's algorithm
The results of BFS algorithm with the same input
We can see that both results are quite different as the BFS traversed from 0->1->3->0 while Dijkstra reached the target vertices directly from the Depot (The Depot is directly connected to each customer and it has shortest distance for each vertex from the start). Although the Dijkstra's algorithm has found the shortest path for each vertex, the tour cost is higher compare to BFS because we need to return to depot after reaching the target vertex. Also, the number of vehicles required for Dijkstra is the same as the number of customer which is 4 in this case. While BFS only required 3 vehicles.
So is it suitable for me to use Dijkstra's algorithm as my extra algorithm or should I try another algorithm to solve this problem? Thank you for spending your time answering my questions.