c# - 如果仅删除一条边，Dijkstra 最短路径快速重新计算

Question

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

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

这意味着:

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

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

问题:

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

• 是否有一种算法可以让我在起始节点仅更改为它的邻居之一时快速重新计算最短路径？

• 是否有其他算法可能更适合我的问题？

谢谢你的帮助

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

Answer 1

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* (有时，不太常见，称为增量 A*。该论文的标题已过时)。这是对 A* 的(相当复杂)修改，允许在仅少数边缘发生变化时快速重新计算最佳路径。

与 A* 一样，LPA* 需要 admissible distance heuristic .如果不存在这样的启发式算法，您可以将其设置为 0。在 A* 中这样做实际上会将其转变为 Djikstra 算法；在 LPA* 中执行此操作会将其变成一种晦涩难懂、很少使用的算法，称为 DynamicSWSF-SP .

---

对于第二种情况，您正在寻找 D*-Lite .这是对 LPA* 的一个非常简单的修改(简单，至少，一旦你理解了 LPA*)，随着单元从开始到结束移动并获得新信息，它会进行增量寻路 (边缘被添加/删除/更改)。它主要用于穿越未知或部分已知地形的机器人。

---

我已经针对各种寻路算法写了一个相当全面的答案(问题中有论文链接) here .