java - 无法为 bellman-ford 算法生成正确的图形

Question

我有 Bellman - Ford 算法的实现。输入程序提供了一个边列表。没有优化它看起来像这样:

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 次迭代而不是 10000，算法完成它的工作。

这是我的生成代码:

//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

你说的Bellman Ford算法的复杂度是O(|E|*|V|)。在您的生成器中，添加边的概率可以忽略不计 (0.005)，这就是我认为代码运行速度很快的原因。

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