LiK*_*Kao 6 algorithm graph shortest-path
我有一个图表,我经常需要知道所有最短的路径(或更确切地说它们的长度).因为我不想重新计算它们,所以我将它们存储在一个简单的数组中,然后从那里检索它们.但是,由于图表可能也会随着时间的推移而改变,因此我必须在给定时间重新计算它们.
目前可能会发生以下变化:
将节点和边缘添加到图形中
改变边缘的长度
添加图表的新边缘
删除边缘或删除节点
在所有情况下,所有节点将始终连接,并且所有边缘都具有正权重.该图也是无向的.操作顺序是这样的,所有节点将始终来自图的同一组件.如果在添加其他节点和边之前删除节点或边缘,则图形永远不会分开.
目前我计划只进行更新,然后通过图形结构传播所有更改.但是我不确定如何正确处理这个问题.您将如何尝试实现缓存长度的这些更新.
编辑:
正如你们中的一些人所指出的那样,在添加节点或更改链接时重新计算所有内容可能是必要的.例如,当所有距离通过更新改变时.但是,如果我只是通过图表传播更改并按照dijkstras的方式进行放松,我可能需要多次放松同一个节点,因为我可能不会选择最佳顺序.问题是如何订购放松步骤,所以我尽可能避免多次更新.
如果没有我想到的实际想法,我不确定这有多大意义,但我希望这可以澄清更多.