相关疑难解决方法(0)

我正在尝试计算最短路径.这适用于下面粘贴的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 = …

我有一个互连边缘列表(E),如何找到从一个顶点连接到另一个顶点的最短路径？

我正在考虑使用最低共同的祖先,但边缘没有明确定义的根,所以我认为解决方案不起作用.

最短路径由遍历的最小顶点数定义.

注意:可能存在连接两个顶点的多路径,因此显然广度优先搜索将不起作用