Geek Answers Handbook

Fast recalculation of shortest Dijkstra paths if only the edge is removed

I am trying to calculate the shortest paths. This works with the Dijkstra implementation below. However, I want to speed it up.

I use this implementation to decide in which area I want to go further. A graph is a two-dimensional array in which all fields are connected to each neighbor. But over time, the following happens: I need to remove some edges (there are obstacles). The beginning of node is my current position, which also changes over time.

It means:

  • I never add a node, never add a new edge, never changing the edge weight. The only operation is to remove the edge.

  • The beginning of a node changes over time

Questions:

  • Is there an algorithm that can perform a quick recount of shortest paths when I know that the only change in the graph is to remove an edge?

  • Is there an algorithm that allows you to quickly recount the shortest path when the beginning of a node changes only to one of its neighbors?

  • Is another algorithm more suitable for my problem?

thanks for your help

using System; using System.Collections.Generic; using System.Collections.ObjectModel; using System.Text; public class Dijkstra<T> { private Node<T> calculatedStart; private ReadOnlyCollection<Node<T>> Nodes { get ; set ; } private ReadOnlyCollection<Edge<T>> Edges { get; set; } private List<Node<T>> NodesToInspect { get; set ; } private Dictionary<Node<T>, int> Distance { get ; set ; } private Dictionary<Node<T>, Node<T>> PreviousNode { get; set ; } public Dijkstra (ReadOnlyCollection<Edge<T>> edges, ReadOnlyCollection<Node<T>> nodes) { Edges = edges; Nodes = nodes; NodesToInspect = new List<Node<T>> (); Distance = new Dictionary<Node<T>, int> (); PreviousNode = new Dictionary<Node<T>, Node<T>> (); foreach (Node<T> n in Nodes) { PreviousNode.Add (n, null); NodesToInspect.Add (n); Distance.Add (n, int.MaxValue); } } public LinkedList<T> GetPath (T start, T destination) { Node<T> startNode = new Node<T> (start); Node<T> destinationNode = new Node<T> (destination); CalculateAllShortestDistances (startNode); // building path going back from the destination to the start always taking the nearest node LinkedList<T> path = new LinkedList<T> (); path.AddFirst (destinationNode.Value); while (PreviousNode[destinationNode] != null) { destinationNode = PreviousNode [destinationNode]; path.AddFirst (destinationNode.Value); } path.RemoveFirst (); return path; } private void CalculateAllShortestDistances (Node<T> startNode) { if (startNode.Value.Equals (calculatedStart)) { return; } Distance [startNode] = 0; while (NodesToInspect.Count > 0) { Node<T> nearestNode = GetNodeWithSmallestDistance (); // if we cannot find another node with the function above we can exit the algorithm and clear the // nodes to inspect because they would not be reachable from the start or will not be able to shorten the paths... // this algorithm does also implicitly kind of calculate the minimum spanning tree... if (nearestNode == null) { NodesToInspect.Clear (); } else { foreach (Node<T> neighbour in GetNeighborsFromNodesToInspect(nearestNode)) { // calculate distance with the currently inspected neighbour int dist = Distance [nearestNode] + GetDirectDistanceBetween (nearestNode, neighbour); // set the neighbour as shortest if it is better than the current shortest distance if (dist < Distance [neighbour]) { Distance [neighbour] = dist; PreviousNode [neighbour] = nearestNode; } } NodesToInspect.Remove (nearestNode); } } calculatedStart = startNode; } private Node<T> GetNodeWithSmallestDistance () { int distance = int.MaxValue; Node<T> smallest = null; foreach (Node<T> inspectedNode in NodesToInspect) { if (Distance [inspectedNode] < distance) { distance = Distance [inspectedNode]; smallest = inspectedNode; } } return smallest; } private List<Node<T>> GetNeighborsFromNodesToInspect (Node<T> n) { List<Node<T>> neighbors = new List<Node<T>> (); foreach (Edge<T> e in Edges) { if (e.Start.Equals (n) && NodesToInspect.Contains (n)) { neighbors.Add (e.End); } } return neighbors; } private int GetDirectDistanceBetween (Node<T> startNode, Node<T> endNode) { foreach (Edge<T> e in Edges) { if (e.Start.Equals (startNode) && e.End.Equals (endNode)) { return e.Distance; } } return int.MaxValue; } }
+4
source share
1 answer

Is there an algorithm that can perform a quick recount of shortest paths when I know that the only change in the graph is to remove an edge?

Is there an algorithm that allows you to quickly recount the shortest path when the beginning of a node changes only to one of its neighbors?

The answer to both of these questions is yes.

In the first case, the algorithm you are looking for is called LPA * (sometimes, less commonly, called Incremental A *. The name on this document is outdated). This is a (rather complicated) modification of A *, which allows you to quickly recalculate the best paths when only a few edges have changed.

Like A *, LPA * requires a valid heuristic distance . If such a heuristic does not exist, you can simply set it to 0. Performing this in * essentially turns it into a Jikstra algorithm; this in LPA * will turn it into an obscure, rarely used algorithm called DynamicSWSF-SP .

In the second case, you are looking for D * -Lite . This is a fairly simple modification for LPA * (simple, at least after you understand LPA *), which provides incremental tracking of the path when the device moves from beginning to end and receives new information (edges are added / deleted / changed). It is mainly used for robots crossing an unknown or partially known landscape.

I wrote a rather detailed answer (with links to articles in the question) about various path search algorithms here .

+7
source

More articles:


All Articles