1

我有一个 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 次迭代而不是 1 万次，那么算法就完成了它的工作。

这是我的生成代码：

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

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

4

1 回答 1

1

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

增加概率，应该有更多的边缘，因此贝尔曼福特将需要更长的时间。

于 2016-05-12T15:41:18.140 回答