All geek questions in one place

Modified Shortest Path Using Dijkstra or Bellman-Ford Algorithm

How can we use the Dijkstra or Bellman-Ford algorithm to find the shortest path in a graph whose some of the edges are affected if we go to certain vertices. Thus, the length of the damaged edge will be greater or less than the original length.

+3
source share
1 answer

If I understand this right, you want to change the cost of the edge in the graph depending on the nodes that are visited in your current path. Example from comments:

"Edge AB has a length of 3, but if you also visit node C, the length of AB will be 5"

, , Djikstra, , "" node . , "" node (- , ), , , , , NP , , Dijikstra. +1 .

+1

Source: https://habr.com/ru/post/1782084/

More articles:


All Articles