开发者

Modified shortest path using Dijkstra's or Bellman–Ford's algorithm

How can we use Dijkstra's or Bellman–Ford's algorithm to find shortest path in a graph whose some of edges are affected if we go specific vertices. Such that, the affected edge's length will be more than or less than the 开发者_如何学编程original length.


If I understand this right, you want to change the cost of an edge in a graph depending on nodes which are visited in your current path. An example from the comments is:

"Edge AB has length 3, but if you also visit node C, AB's length will be 5"

Now, there doesn't seem to be a way for something like Djikstra's algorithm to be used as there is a greedy step in that algorithm which picks the 'best' node at every stage. The notion that the 'best' node at that point may change at a later time (due to a rule such as above) violates the concept of the greedy approach which assumes that we are effectively visiting nodes in order from best to worst cost. I'm not certain if this is NP hard as suggested but it certainly cannot use a Dijikstra kind of approach from the start. +1 for the problem though.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜