0

我在 Dijkstras 算法中有类似的东西，但我没有得到任何错误。我尝试用不同的值代替整数最大值和其他各种东西，但没有任何效果。我也搜索了这个网站和其他网站，但没有发现任何帮助。此外，如果它有所作为，我的图形类本身就是一个类。任何帮助，将不胜感激。我更新了我的问题......问题得到了回答。但我确实重新格式化以防万一其他人想看一下。

          public static void main(String[] args)
              {

                  final static int V=7;
                  static final int E=13;

                 Graph graph=new Graph(V,E);

                graph.edge[0].src = 1; 
                graph.edge[0].dest = 2; 
                graph.edge[0].weight = 5; 

                graph.edge[1].src = 1; 
                graph.edge[1].dest = 3; 
                graph.edge[1].weight = 8; 

                graph.edge[2].src = 1; 
                graph.edge[2].dest = 5; 
                graph.edge[2].weight = 7; 

                graph.edge[3].src = 1; 
                graph.edge[3].dest = 6; 
                graph.edge[3].weight = 10; 

                graph.edge[4].src = 2; 
                graph.edge[4].dest = 3; 
                graph.edge[4].weight = -2; 

                graph.edge[5].src = 2; 
                graph.edge[5].dest = 5; 
                graph.edge[5].weight = -2; 

                graph.edge[6].src = 3; 
                graph.edge[6].dest = 4; 
                graph.edge[6].weight = 6; 

                graph.edge[7].src = 5; 
                graph.edge[7].dest = 4; 
                graph.edge[7].weight = 4; 

                graph.edge[8].src = 5; 
                graph.edge[8].dest = 6; 
                graph.edge[8].weight = 2;

                graph.edge[9].src = 5; 
                graph.edge[9].dest = 7; 
                graph.edge[9].weight = 7;

                graph.edge[10].src = 6; 
                graph.edge[10].dest = 7; 
                graph.edge[10].weight= -1; 

                graph.edge[11].src = 7; 
                graph.edge[11].dest = 3; 
                graph.edge[11].weight = 4;

                graph.edge[12].src = 7; 
                graph.edge[12].dest = 4; 
                graph.edge[12].weight = 5;




         Graph.BellmanFord(graph,0);

      }



          public class Graph 
       {


          public class Edge { 
          int src, dest, weight; 
           Edge() { 
          src = dest = weight = 0; 
        } 
       }; 

       int V, E; 
       Edge edge[]; 

       Graph(int v, int e) 
        { 
        V = v; 
        E = e; 
        edge = new Edge[e]; 
       for (int i=0; i<e; ++i) 
           edge[i] = new Edge(); 
      }



      static void bellmanford(Graph graph , int src )
       {

         int V = graph.V, E = graph.E; 
         int dist[]=new int[V];

          for (int i=0; i<V; ++i) 
          dist[i] = Integer.MAX_VALUE; 
          dist[src] = 0; 



        for (int i=1; i<V; ++i) 
       { 
       for (int j=0; j<E; ++j) 
       { 
         int u = graph.edge[j].src; 
         int v = graph.edge[j].dest; 
         int weight = graph.edge[j].weight; 
         if (dist[u]!=Integer.MAX_VALUE && // I’m getting the error        
         here.
               dist[u]+weight<dist[v]) 
                dist[v]=dist[u]+weight; 
        } 
        } 

        for (int j=0; j<E; ++j) 
        { 
       int u = graph.edge[j].src; 
       int v = graph.edge[j].dest; 
       int weight = graph.edge[j].weight; 
       if (dist[u]!= Integer.MAX_VALUE && 
       dist[u]+weight < dist[v]) 
       System.out.println("Graph contains negative weight cycle"); 


        }

         printdistb(dist,V);
       }


     static void printdistb(int dist[], int V) 
     { 
    System.out.println("Vertex   Distance from Source"); 
    for (int i = 0; i< V; ++i) 
    System.out.println(i+"            "+dist[i]); 
     }
4

1 回答 1

0

您正在声明dist[]长度为V. 然后您将graph.edge[j].src其用作dist[]数组的索引。这就是为什么你得到一个ArrayIndexOutOfBoundsException. 简而言之，这意味着 src 值大于 V。

修复

增加dist[]1 的长度。

内部static void bellmanford(){...} 变化从

int dist[] = new int[V];

至

int dist[] = new int[V+1];

这确实为我解决了异常问题。但是该算法似乎存在更多逻辑问题（实际问题可能隐藏在其他地方更深。）。但至少程序现在正在执行，所以你可以调试它。祝你好运。

于 2018-12-11T01:18:08.773 回答