Kann rechten Graphen für Bellman-Ford-Algorithmus nicht erzeugen

Question

Ich habe eine Implementierung des Algorithmus von Bellman - Ford. Das Eingabeprogramm lieferte eine Liste von Kanten. Ohne Optimierung sieht es wie folgt aus:

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

es die Komplexität von O (V * E) Aber mit der Optimierung seiner Werke sehr schnell hat. es sieht aus wie

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

In der Praxis, wenn die Anzahl der Ecken, zum Beispiel zehntausend, in der äußeren Schleife nur hatte passiert 10-12 Wiederholungen statt 10 Tausend, und der Algorithmus seine Arbeit abgeschlossen.

Dies ist mein Code generieren:

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

Aber ich brauche eine Grafik zu erzeugen, auf dem es nicht so schnell sein wird, seine Arbeit zu beenden. Das kann im Generator geändert werden?

Answer 1

Die Komplexität von Bellman Ford Algorithmus wie Sie sagten, ist O (| E | * | V |). In Ihrem Generator ist die Wahrscheinlichkeit, eine Kante hinzuzufügen, vernachlässigbar (0,005), weshalb der Code meiner Meinung nach schnell arbeitet.

Erhöhen Sie die Wahrscheinlichkeit, es soll mehr Kanten geben und folglich sollte der Bellman Ford dann längere Zeit brauchen.