我的问题是我的任务是设计一个有效的算法，给出任何无向加权图G =（V，E，L）两个节点s，t∈V，最大边长L作为输入答案是否可以到达节点是否来自节点 . 困难的部分是我的算法应该在时间O（n m）运行！
我已经有了一个公平的想法，我相信我需要使用深度优先搜索，它使用O（1）操作进行调整以保持运行时间 . 我的感觉是我需要在标准深度优先搜索中添加条件测试，找到两个节点之间的路径以比较L <= currentEdgeLength，并且如果此条件为真，则仅将新节点添加到路径 .
任何投入将不胜感激！
DFS和BFS的复杂性为O（n m），因此您可以为每个查询运行新搜索 . 你提出的正是我解决这个问题的方式 .
1 回答
DFS和BFS的复杂性为O（n m），因此您可以为每个查询运行新搜索 . 你提出的正是我解决这个问题的方式 .