A heuristic for shortest path with fewest number of edges?

#1

Hi,

I am working on problem 19.10 in version 1.4.8 of the book. The question is about finding the shortest path but if there are multiple shortest paths of the same length, it should return the path with the least number of edges in it.

I came up with a heuristic which basically adds a weight x to every edge where x = minEdgeWeight/(total number of edges + 1). After this, I claim that running Dijkstra on this updated graph will return the correct answer.

I am not able to prove/disprove this claim formally. Any hints on how to proceed?

Cheers,
Pankaj

0 Likes
#2

Hey Pankaj,

I think your idea is basically Lagrange relaxation (https://en.wikipedia.org/wiki/Lagrangian_relaxation). Personally I think it should work if you design your cost function well, it will combine multiple constraints into one only.

Here, I think your new cost function should work perfectly. One thing you could try is implementing your idea and then compare it will our program. I think it might be an interesting experience, and you should try it.

0 Likes
#3

Hi,

I did try my approach and it worked on the test cases that I used. I have not found a counter example to disprove it yet. Do you think we can prove this hypothesis using Lagrange Relaxation?

0 Likes
#4

I would recommend you to try on some randomly generated graph such that you can test it more. Few test cases do not sufficiently prove your algorithm is experimentally correct in my opinion :smile:

0 Likes