roc*_*cko 2 c c++ algorithm graph
是否可以在带有循环和负边的无向图中使用BFS(使用遍历的最小顶点)在O(log n)时间内从源中找到目的地？
例如:给出一个简单的连通图G,其中包含N个顶点和N个边(一个简单的图是一个没有循环且在任意两个不同顶点之间不超过一条边的无向图).很明显,图G只包含一个周期,你可以假设这个周期的长度是奇数(这个周期中有奇数个顶点).顶点从1到N编号.每个边被分配相应的整数权重.您的任务是激发两种类型的查询:更新由fuv表示的查询:更改最短路径上边缘的所有权重的符号(稍后可以看到此问题中最短路径的定义)从顶点u到顶点v.查找由？表示的查询？uv:在从顶点u到顶点v的最短路径上,找到(可能为空)一组连续边,使得权重之和最大.换句话说,让我们将从u到v的最短路径定义为a_1,a_2,...,a_k(其中a_1 = u和a_k = v).你必须找到a_i和a_j使得i <= j并且路径a_i,a_(i + 1),...,a_j的边缘的权重之和尽可能大.你只需要找到这笔钱.两个顶点u和v之间的最短路径是将它们与最小数量的顶点连接起来的路径.在这个问题中,显然在G的任何一对顶点之间只有一条最短路径.
让G与顶点集的图V和边集E.那么广度优先搜索(BFS)的最坏情况下的时间复杂度是O(|V|+|E|).时间复杂度是O(|V|+|E|),因为在最坏的情况下访问每个顶点和边缘.复杂度O(| E |)可以在O(| V |)和O(| V 2 |)之间变化.在稀疏图的情况下,复杂度将近似为O(| V |),并且在密集图的情况下,复杂度将近似为O(| V 2 |).