0
$\begingroup$

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained by BFS.

Here, I consider that each weight of the edge is the minimum of the end vertices and the weight of the path is the sum of the edges divided by the number of edges on the path.

I am unable to use BFS for such algorithm. Please suggest me a suitable known algorithm to solve such problem. The following problem is solved manually, but I wish to solve it by using some known algorithm. enter image description here

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Programming questions are off-topic here. I have removed the programming part. If you want a programming solution, you can delete the post and may re-ask it on StackOverflow (though I'm not sure if it would be treated too broad there). $\endgroup$ – xskxzr Apr 25 '19 at 13:13
  • 1
    $\begingroup$ You can use Dijkstra algorithm to solve the problem with some modification while 'relaxing' edges. $\endgroup$ – Mr. Sigma. Apr 25 '19 at 15:11
  • $\begingroup$ Related: cs.stackexchange.com/q/108487/68251 $\endgroup$ – ryan Apr 25 '19 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.