3

任何人都可以帮助使用 java 中的贝尔曼福特算法来计算从源顶点开始的最短路径。

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

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 ");
        }
    }
}
4

1 回答 1

8

按照标准算法，我觉得应该给前人介绍一个数组：

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

正如预期的那样

于 2013-03-28T12:49:59.297 回答