不能为bellman-ford算法生成正确的图

Question

我有一个贝尔曼-福特算法的实现。输入程序提供了一个边缘列表。在没有优化的情况下，它看起来像这样：

int i, j;
        for (i = 0; i < number_of_vertices; i++) {
            distances[i] = MAX;
        }
        distances[source] = 0;
        for (i = 1; i < number_of_vertices - 1; ++i) {

            for (j = 0; j < e; ++j) { //here i am calculating the shortest path
                if (distances[edges.get(j).source] + edges.get(j).weight < distances[edges.get(j).destination]) {
                    distances[edges.get(j).destination] = distances[edges.get(j).source] + edges.get(j).weight;
                }
            }
        }

它具有O(V * E)的复杂度，但经过优化后，他的工作速度非常快。看起来像是

while (true) {

            boolean any = false;
            for (j = 0; j < e; ++j) { //here i am calculating the shortest path
                if (distances[edges.get(j).source] + edges.get(j).weight < distances[edges.get(j).destination]) {
                    distances[edges.get(j).destination] = distances[edges.get(j).source] + edges.get(j).weight;
                    any = true;
                }
            }
            if (!any) break;
        }

在实践中，如果外部循环中的顶点数量，例如一万个，只有10-12次迭代，而不是一万次，并且算法完成了它的工作。

这是我的生成代码：

//q - vertices

for (int q = 100; q <= 20000; q += 100) {
          List<Edge> edges = new ArrayList();
                for (int i = 0; i < q; i++) {
                    for (int j = 0; j < q; j++) {
                        if (i == j) {
                            continue;
                        }

                        double random = Math.random();
                        if (random < 0.005) {
                            int x = ThreadLocalRandom.current().nextInt(1, 100000);
                           edges.add(new Edge(i, j, x));
                            edges++;
                        }
                    }

                }
              //write edges to file edges
            }

但我需要生成一个图表，在这个图表上完成他的工作不会那么快。可以在生成器中进行更改吗？

Answer 1

就像你说的，贝尔曼福特算法的复杂度是O(|E|*|V|)。在您的生成器中，添加边的概率可以忽略不计(0.005)，这就是为什么根据我的说法，代码运行得很快。

增加概率，将有更多的边缘，因此Bellman福特将花费更长的时间。