如果仅删除边缘，则Dijkstra最短路径快速重新计算 [英] Dijkstra Shortest-Paths fast recalculation if only an edge got removed

问题描述

我正在尝试计算最短路径。这确实适用于下面粘贴的Dijkstra实现。但是我想加快速度。

I'm trying to calculate the shortest paths. This does work with the below pasted implementation of Dijkstra. However I want to speed the things up.

我使用此实现方式来确定下一个要转到的字段。该图表示一个二维数组，其中所有字段都连接到每个邻居。但是随着时间的流逝，会发生以下情况：我需要去除一些边缘（有障碍物）。起始节点是我当前的位置，它也会随着时间而变化。

I use this implementation to decide to which field I want to go next. The graph represents an two dimensional array where all fields are connected to each neighbours. But over time the following happens: I need to remove some edges (there are obstacles). The start node is my current position which does also change over time.

这意味着：

• 我从不添加节点，从不添加新边，也不会更改边的权重。唯一的操作是删除边缘

• I do never add a node, never add a new edge, never change the weight of an edge. The only operation is removing an edge

起始节点确实会随时间变化

The start node does change over time

问题：

• 是否有一种算法可以快速重新计算最短的-当我知道图形中唯一的变化是去除了一条边时的路径？

• Is there an algorithm wich can do a fast recalculation of the shortest-paths when I know that the only change in the graph is the removal of an edge?

是否存在一种算法允许我快速重新计算最短路径？

Is there an algorithm wich allows me to fast recalculate the shortest path when the start node changes only to one of it's neighbours?

另一种算法也许更适合我的问题？

Is another algorithm maybe better suited for my problem?

Thx为您提供帮助

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;
    }
}

推荐答案

当我知道图形中唯一的变化是边缘的去除时，是否有一种算法可以对最短路径进行快速重新计算？

Is there an algorithm wich can do a fast recalculation of the shortest-paths when I know that the only change in the graph is the removal of an edge?

当起始节点仅更改为邻居中的一个时，有什么算法可以让我快速重新计算最短路径？

Is there an algorithm wich allows me to fast recalculate the shortest path when the start node changes only to one of it's neighbours?

这两个问题的答案是。

对于第一种情况，您要查找的算法称为 LPA * （有时，不太常见，称为Incremental A *。该文件的标题已过时）。这是对A *的（相当复杂）的修改，当只有少数边缘发生变化时，可以快速重新计算最佳路径。

For the first case, the algorithm you're looking for is called LPA* (sometimes, less commonly, called Incremental A*. The title on that paper is outdated). It's a (rather complicated) modification to A* that allows fast recalculation of best paths when only a few edges have changed.

像A *一样，LPA *需要允许的距离启发式。如果不存在这种试探法，则可以将其设置为0。在A *中执行此操作实际上会将其转变为Djikstra的算法；在LPA *中执行此操作会将其转变为一种晦涩且很少使用的算法，称为 DynamicSWSF-SP 。

Like A*, LPA* requires an admissible distance heuristic. If no such heuristic exists, you can just set it to 0. Doing this in A* will essentially turn it into Djikstra's algorithm; doing this in LPA* will turn it into an obscure, rarely-used algorithm called DynamicSWSF-SP.

对于第二种情况，您正在寻找 D * -Lite 。这是对LPA * （至少，一旦您了解LPA *，至少很简单）的相当简单的修改，它随着单位从头到尾移动并获取新信息而进行增量寻路。 （添加/删除/更改边）。它主要用于穿越未知或部分已知地形的机器人。

For the second case, you're looking for D*-Lite. It is a pretty simple modification to LPA* (simple, at least, once you understand LPA*) that does incremental pathfinding as the unit moves from start-to-finish and new information is gained (edges are added/removed/changed). It is primarily used for robots traversing an unknown or partially-known terrain.

我已经写了一个相当全面的答案（带有指向各种问题中的论文），其中包括各种寻路算法此处。

I've written up a fairly comprehensive answer (with links to papers, in the question) on various pathfinding algorithms here.

这篇关于如果仅删除边缘，则Dijkstra最短路径快速重新计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！