每次迭代的Bellman Ford顯示前驅

Question

這裏前驅頂點顯示所有迭代。我想要最終的前輩顯示爲頂點

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) 
        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; 
         /*Gives me the predecessor nodes of all iterations How can i get the final predecessornodes*/                          System.out.println(edges.get(j).v+" Has predecessor " + 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; 
     } 
     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+"to"+i+" ==> "+r.d[i]); 
      else 
      System.out.println(" There is a nagative edge cycle "); 
     } 
} 

錯誤的輸出如下。我想打印出來的前身爲每個迭代：

**OUTPUT:** 

Enter number of vertices 
Cost Matrix 
0 
-1 
4 
0 
0 
0 
0 
3 
2 
2 
0 
0 
0 
0 
0 
0 
1 
5 
0 
0 
0 
0 
0 
-3 
0 
Enter the source vertex 
1 Has predecessor 0 
2 Has predecessor 0 
2 Has predecessor 1 
3 Has predecessor 1 
4 Has predecessor 1 
3 Has predecessor 4 
0to0 ==> 0 
0to1 ==> -1 
0to2 ==> 2 
0to3 ==> -2 
0to4 ==> 1 

Answer 1

看來你的最後幾行是非常少的理解，所以我給你我的計劃，我做了幾天就回來..你可以查找錯誤你的程序使得它很難理解100行代碼並找出錯誤：
另外，我建議你更注重編寫整潔和註釋的代碼，而不是直接關注時間優化。只檢查邏輯和嘗試實施它在你的代碼，這就是爲什麼我沒有張貼的Java代碼，這樣您就可以輕鬆搞定一切:)

// A C/C++ program for Bellman-Ford's single source shortest path algorithm. 

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <limits.h> 

// a structure to represent a weighted edge in graph 
struct Edge 
{ 
    int src, dest, weight; 
}; 

// a structure to represent a connected, directed and weighted graph 
struct Graph 
{ 
    // V-> Number of vertices, E-> Number of edges 
    int V, E; 

    // graph is represented as an array of edges. 
    struct Edge* edge; 
}; 

// Creates a graph with V vertices and E edges 
struct Graph* createGraph(int V, int E) 
{ 
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); 
    graph->V = V; 
    graph->E = E; 

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge)); 

    return graph; 
} 

// A utility function used to print the solution 
void printArr(int dist[], int n) 
{ 
    printf("Vertex Distance from Source\n"); 
    for (int i = 0; i < n; ++i) 
     printf("%d \t\t %d\n", i, dist[i]); 
} 

// The main function that finds shortest distances from src to all other 
// vertices using Bellman-Ford algorithm. The function also detects negative 
// weight cycle 
void BellmanFord(struct Graph* graph, int src) 
{ 
    int V = graph->V; 
    int E = graph->E; 
    int dist[V]; 

    // Step 1: Initialize distances from src to all other vertices as INFINITE 
    for (int i = 0; i < V; i++) 
     dist[i] = INT_MAX; 
    dist[src] = 0; 

    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src 
    // to any other vertex can have at-most |V| - 1 edges 
    for (int i = 1; i <= V-1; 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] + weight < dist[v]) 
       dist[v] = dist[u] + weight; 
     } 
    } 

    // Step 3: check for negative-weight cycles. The above step guarantees 
    // shortest distances if graph doesn't contain negative weight cycle. 
    // If we get a shorter path, then there is a cycle. 
    for (int i = 0; i < E; i++) 
    { 
     int u = graph->edge[i].src; 
     int v = graph->edge[i].dest; 
     int weight = graph->edge[i].weight; 
     if (dist[u] + weight < dist[v]) 
      printf("Graph contains negative weight cycle"); 
    } 

    printArr(dist, V); 

    return; 
} 

// Driver program to test above functions 
int main() 
{ 

    int V = 5; // Number of vertices in graph 
    int E = 8; // Number of edges in graph 
    struct Graph* graph = createGraph(V, E); 

    // add edge 0-1 
    graph->edge[0].src = 0; 
    graph->edge[0].dest = 1; 
    graph->edge[0].weight = -1; 

    // add edge 0-2 
    graph->edge[1].src = 0; 
    graph->edge[1].dest = 2; 
    graph->edge[1].weight = 4; 

    // add edge 1-2 
    graph->edge[2].src = 1; 
    graph->edge[2].dest = 2; 
    graph->edge[2].weight = 3; 

    // add edge 1-3 
    graph->edge[3].src = 1; 
    graph->edge[3].dest = 3; 
    graph->edge[3].weight = 2; 

    // add edge 1-4 
    graph->edge[4].src = 1; 
    graph->edge[4].dest = 4; 
    graph->edge[4].weight = 2; 

    // add edge 3-2 
    graph->edge[5].src = 3; 
    graph->edge[5].dest = 2; 
    graph->edge[5].weight = 5; 

    // add edge 3-1 
    graph->edge[6].src = 3; 
    graph->edge[6].dest = 1; 
    graph->edge[6].weight = 1; 

    // add edge 4-3 
    graph->edge[7].src = 4; 
    graph->edge[7].dest = 3; 
    graph->edge[7].weight = -3; 

    BellmanFord(graph, 0); 

    return 0; 
}