是否存在给定开始(v)和结束(u)的图算法将找到通过给定边集的最短路径,但是如果u是断开连接的顶点,它还将确定添加缺失边的最短路径,直到你不再断开了？
我有一个像素矩阵,其中的行由255(黑色)和0(白色)组成.线条(255)可以有断裂或刺激,我必须摆脱两者.我可以有一个像素矩阵森林,有7个左右的黑色像素树.我需要找到每棵树的真实终点,找到每棵树的单个最短路径,然后将所有倾斜树合并在一起形成1条单线(即,从原始矩阵中最远的2个端点开始的单条最短路径) .所有边缘权重都可以被认为是1.
谢谢
如何运行Dijkstra的算法,如果断开连接,连接v和u？您对"添加缺失边缘的最佳位置"的标准是什么？边缘是否有重量(如距离)？
编辑:对于"最佳位置"的一个想法,您可以尝试在所有连接对之间具有最小路径的最小路径的路径.Floyd-Warshall算法可用于查找所有对之间的最短路径.因此,为v的树和u中的每个节点运行Floyd-Warshall.
| 归档时间： |
|
| 查看次数： |
2587 次 |
| 最近记录： |