是否可以在具有循环和负边的无向图中使用BFS(使用遍历的最小顶点)在O(log n)时间从源中找到目标？
例如:
您将获得一个具有N个顶点和N个边的简单连接图G(一个简单图是无向图，它没有环，并且在任意两个不同顶点之间不超过一个边)。
显然，图G恰好包含一个循环，您可以假定该循环的长度为奇数(此循环中的顶点数为奇数)。
顶点的编号从1到N。为每个边缘分配一个相应的整数权重。
您的任务是激发两种类型的查询:
更新由f u v表示的查询:将最短路径上的所有边缘权重的符号(以后将在此问题中看到最短路径的定义)从顶点u更改为顶点v。
查找以？表示的查询u v:在从顶点u到顶点v的最短路径上，找到(可能为空)连续边集，以使权重之和最大。换句话说，让我们定义从u到v的最短路径为a_1，a_2，...，a_k(其中a_1 = u和a_k = v)。您必须找到a_i和a_j，以使i 两个顶点u和v之间的最短路径是用最小数量的顶点连接它们的路径。在这个问题中，很明显，在G的任意一对顶点之间只有一条最短的路径。
最佳答案
令G为具有Vertex设置V和Edge设置E的图。那么，在最坏情况下广度优先搜索(BFS)的时间复杂度为O(|V|+|E|)。时间复杂度为O(|V|+|E|)，因为在最坏的情况下访问每个顶点和边。复杂度O(| E |)可以在 O(| V |)和 O(| V2 |)之间变化。在稀疏图的情况下，复杂度大约为 O(| V |)，在密集图的情况下，复杂度大约为 O(| V2 |)。