Geek Answers Handbook

Dijkstra variant with k nodes?

I need to find the minimum path from the source and destination, where the source and destination are the same node, and I need the minimum fixed number of nodes in the path. I decided to implement Dijkstra's algorithm (in Java) with an option in which k nodes are included in the minimum path. (k is the minimum number of nodes to cover). It is right? If yes, then any suggestion for implementation? thanks in advance

+5
source share
1 answer

This is a good idea. Remember to set the distance to the source in INF instead of 0 at the beginning for the correct result.

EDIT

A simple solution is to start with u, go to all adjacent vertices and return to adjacent vertices with k as k-1, source as an adjacent vertex and destination as v. The following is an implementation of this simple solution in C ++. GeeksForGeeks

+2
source

More articles:


All Articles