主页 / coding / 问题

问题[graph-theory](coding)

Martin Hope
Elijah Crum
Asked: 2025-04-02 05:11:21 +0800 CST
  • 6

我正在研究此处描述的 Anytime Dynamic A* 算法的实现。我完成了初始基本实现的约 50%，但停留在以下行：

在该程序的ComputePath第 19 行中

如果 s′ 在此之前没有被访问过

这是我能找到的唯一一行提到“访问”节点的内容。“访问”是什么意思？我是否需要为每个节点添加一个visited布尔值？如果需要，我什么时候才能使节点被访​​问或未被访问？

我确信这没关系，但我用 Java 21 编写了这个实现

graph-theory
Martin Hope
Mike Mathcook
Asked: 2024-07-06 10:05:57 +0800 CST
  • 5

以下代码的复杂度是多少？是 O(n^3log(n)) 吗？

#G is an undirected dense graph, which has N vertices.
import networkx as nx
def cal_minimax_path_matrix(G):
    MST = nx.minimum_spanning_tree(G)
    minimax_matrix = np.zeros((N, N))

    for i in range(N):
        for j in range(N):
            if j > i:
                max_weight = -1 
                path = nx.shortest_path(MST, source=i, target=j)
                for k in range(len(path)-1):
                    if( MST.edges[path[k],path[k+1]]['weight'] > max_weight):
                        max_weight = MST.edges[path[k],path[k+1]]['weight']
                minimax_matrix[i,j] = minimax_matrix[j,i] = max_weight
                
    return minimax_matrix

构建最小生成树的复杂度为 O(n^2)。在最小生成树中查找最短路径的复杂度是多少？是 O(nlog(n)) 吗？

该代码基于 Madhav-99 的代码，请参阅：

https://github.com/Madhav-99/Minimax-Distance

graph-theory