Java中的Bellman Ford算法

Question

任何人都可以帮助java中的bellman ford算法来计算源顶点的最短路径.

我还希望在遍历所有边缘之后为每个节点打印最终更新的前任节点,并且在所有迭代之后这是我的代码

import java.io.*;
import java.util.*;
public class BellmanFord {
    LinkedList<Edge> edges;
    int d[];
    int n,e,s;
    final int INFINITY=999;

    private static class Edge  {
        int u,v,w;

        public Edge(int a, int b, int c)     {
            u=a;
            v=b;
            w=c;
        }
    }

    BellmanFord() throws IOException {
        int item;
        edges = new LinkedList<Edge>();
        BufferedReader inp = new BufferedReader (new InputStreamReader(System.in));

        System.out.print("Enter number of vertices ");
        n = Integer.parseInt(inp.readLine());

        System.out.println("Cost Matrix");
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++)   {
                item = Integer.parseInt(inp.readLine());
                if(item != 0)
                    edges.add(new Edge(i,j,item));
            }
        }

        e = edges.size();
        d = new int[n];

        System.out.print("Enter the source vertex ");
        s = Integer.parseInt(inp.readLine());
    }

    void relax() {
        int i,j;
        for(i=0;i<n;++i)
            d[i]=INFINITY;

        d[s] = 0;
        for (i = 0; i < n - 1; ++i) {
            for (j = 0; j < e; ++j) { //here i am calculating the shortest path
                if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v]) {
                    d[edges.get(j).v] = d[edges.get(j).u] + edges.get(j).w;
                }
             }
         }
    }

    boolean cycle() {
        int j;
        for (j = 0; j < e; ++j)
            if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v])
                 return false;
        return true;
    }

    public static void main(String args[]) throws IOException   {
        BellmanFord r = new BellmanFord();
        r.relax();
        if(r.cycle()) {
            for(int i=0;i<r.n;i++)
                System.out.println(r.s+" ==> "+r.d[i]);
        } else {
            System.out.println(" There is a negative edge cycle ");
        }
    }
}

Answer 1

根据标准算法,我认为你应该为前辈们引入一个数组:

int[] p = new int[n];

在relax函数中初始化:

for(i=0;i<n;++i) {
    d[i] = INFINITY;
    p[i] = -1;
}

并与距离一起更新:

for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < e; ++j) { //here i am calculating the shortest path
        if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v]) {
            d[edges.get(j).v] = d[edges.get(j).u] + edges.get(j).w;
            p[edges.get(j).v] = edges.get(j).u;
        }
    }
}

并打印:

for (int i = 0; i < n; i++) {
    System.out.println("Vertex " + i " has predecessor " + p[i]);
}

编辑因为您的代码片段似乎有问题,所以这里是完整的工作代码:

import java.io.*;
import java.util.*;

public class BellmanFord  {
    LinkedList<Edge> edges;
    int d[], p[];
    int n,e,s;
    final int INFINITY=999;

    private static class Edge  {
        int u,v,w;

        public Edge(int a, int b, int c)     {
            u=a;
            v=b;
            w=c;
        }
    }

    BellmanFord () throws IOException {
        int item;
        edges = new LinkedList<Edge>();
        BufferedReader inp = new BufferedReader (new InputStreamReader(System.in));

        System.out.print("Enter number of vertices ");
        n = Integer.parseInt(inp.readLine());

        System.out.println("Cost Matrix");
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++)   {
                item = Integer.parseInt(inp.readLine());
                if(item != 0)
                    edges.add(new Edge(i,j,item));
            }
        }

        e = edges.size();
        d = new int[n];
        p = new int[n];

        System.out.print("Enter the source vertex ");
        s = Integer.parseInt(inp.readLine());
    }

    void relax() {
        int i,j;
        for(i=0;i<n;++i) {
            d[i]=INFINITY;
            p[i] = -1;
        }

        d[s] = 0;
        for (i = 0; i < n - 1; ++i) {
            for (j = 0; j < e; ++j) { //here i am calculating the shortest path
                if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v]) {
                    d[edges.get(j).v] = d[edges.get(j).u] + edges.get(j).w;
                    p[edges.get(j).v] = edges.get(j).u;
                }
             }
         }
    }

    boolean cycle() {
        int j;
        for (j = 0; j < e; ++j)
            if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v])
                 return false;
        return true;
    }

    void print() {
        for (int i = 0; i < n; i++) {
            System.out.println("Vertex " + i + " has predecessor " + p[i]);
        }
    }

    public static void main(String args[]) throws IOException   {
        BellmanFord  r = new BellmanFord ();
        r.relax();
        if(r.cycle()) {
            for(int i=0;i<r.n;i++)
                System.out.println(r.s+" ==> "+r.d[i]);
        } else {
            System.out.println(" There is a negative edge cycle ");
        }

        r.print();
    }
}

输入:

Enter number of vertices 3
Cost Matrix
0
99
1
4
0
2
2
4
0
Enter the source vertex 0

输出:

0 ==> 0
0 ==> 5
0 ==> 1
Vertex 0 has predecessor -1
Vertex 1 has predecessor 2
Vertex 2 has predecessor 0

这是预期的