java - 判断图 G = (V,E) 是否包含负权环

Question

在这个程序中，我得到一个输入文本文件，其中提供有关加权有向图的信息

G = (V, E, w)

输入中文本文件的第一行存储 V(顶点数)和 E(边数)。

以下行按 u、v、权重的顺序存储有关边 (u、v) 的数据.

我正在尝试实现一个代码，该代码考虑此输入并确定 G 是否包含负权循环。

到目前为止，我已经尝试使用贝尔曼福特算法来尝试让它发挥作用:我首先初始化一个用于初始化距离的dist[]数组从源到所有其他顶点的数字非常高(确保 src 到 src 为 0)。

接下来，我放松所有边缘|V| - 1 次。

最后，我通过再次迭代边数组来检查负权重循环，检查是否获得更短的路径。

但是，当我尝试执行放松边缘的第二步时，我不断收到索引越界错误。

注意:要检查下面的代码，只需向下滚动到 isNegativeCycle() 方法。我只是添加了一些其他内容，以防有人需要背景信息。

public class P1 {
//instance variables
static int V;   //number of vertices
static int E;   //number of edges

//vertex class
public class Vertex {
    int ID; //the name of the vertex
}

//edge class
public class Edge {
    Vertex source;  //the source vertex - its a directed graph
    Vertex dest;    //the destination vertex
    int weight; //the weight of the edge
}


//graph class where all the magic happens
public class Graph { 
    //Each graph has an array of edges
    Edge edgearray[];

    //constructor
    public Graph(int n, int m)  {
        V = n;
        E = m;

        edgearray = new Edge[E];
        for (int i = 0; i < E; i++) { 
            edgearray[i] = new Edge();
        }
    }

    //THIS IS THE IMPORTANT METHOD
    public String isNegativeCycle(Graph G, int src) {
        int dist[] = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;  //cos the distance from A to A is 0

        //Relax all edges
        for (int i = 1; i <= V-1; i++) { 
            for (int j = 0; j < E; j++) { 
                int u = G.edgearray[j].source.ID; 
                int v = G.edgearray[j].dest.ID; 
                int weight = G.edgearray[j].weight; 

            //THIS IS WHERE I GET THE INDEX OUT OF BOUNDS ERROR    
            if (dist[u]!= Integer.MAX_VALUE && (dist[u]+weight) < dist[v]) { 
                    dist[v] = dist[u]+weight; 
            } 
        } 

        //check for a negative cycle
        for (int a = 0; a < E; a++) { 
            int u = G.edgearray[a].source.ID; 
            int v = G.edgearray[a].dest.ID; 
                double weight = G.edgearray[a].weight;

                if (dist[u] != Integer.MAX_VALUE && dist[u]+weight < dist[v])   {
                return "YES";
            }
        } 


        return "NO";
    }


}//end of graph class


//main method 
public static void main(String[] args) {
    P1 instance = new P1();
    int n;
    int m;
    int counter = 0;
    boolean fl = true;
    String infileName = args[0];
    Graph G = instance.new Graph(V, E);

    File infile = new File(infileName);
    Scanner fileReader = null;
    try {
        fileReader = new Scanner(infile);
        while (fileReader.hasNextLine())    {

            //if we're reading the first line
            if (fl == true) {
                String[] temp = fileReader.nextLine().split(" ");
                n = Integer.parseInt(temp[0]);
                V = n;
                m = Integer.parseInt(temp[1]);
                E = m;
                G = instance.new Graph(V, E);
                fl = false;
            }
            //if we're reading any line other than the first line
            else    {
                String[] temp = fileReader.nextLine().split(" ");
                //G.addEdge(temp[0], temp[1], Double.parseDouble(temp[2]));

                Vertex newsrc = instance.new Vertex();
                Vertex newdest = instance.new Vertex();

                newsrc.ID = Integer.parseInt(temp[0]);
                newdest.ID = Integer.parseInt(temp[1]);

                Edge newEdge = instance.new Edge();
                newEdge.source = newsrc;
                newEdge.dest = newdest;
                newEdge.weight = Integer.parseInt(temp[2]);

                G.edgearray[counter] = newEdge;
                counter++;
            }
        }
    }
    catch (FileNotFoundException e) {
        System.out.println("File not found.");  
    }

    System.out.println(G.isNegativeCycle(G, 0));
}
}

此时我当前的输入文件并不重要，但在运行此代码后，我预计输出为“YES”。谢谢!

Answer 1

我应该包含我的输入文件。在我的输入文件中，您会看到顶点名称从 1 开始。因此，当调用 isNegativeCycle 时，我应该发送 1 而不是 0。此外，我将 >dist[] 数组大一号。