Monday, 10 August 2015

Find out minimum cost between two nodes in a weighted graph using greedy approach using java.....

Input :- 1.cost matrix for the graph is given via text file ,just write the matrix in the text file simply like we write normally and save it ,change the path of the file in the program too.

2.For those nodes which don't have direct paths between them corresponding entries in the input adjacency matrix via file should be "-1".
here is the code  ........





       
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ShortestPath {
 public static int count = 0;
 public static int[][] matrix;

 public static void main(String[] args) throws NumberFormatException, IOException {
  // TODO Auto-generated method stub
  File file = new File("C:/Users/gauravy/Desktop/matrix.txt");
  BufferedReader be = new BufferedReader(new FileReader(file));
  while ((be.readLine()) != null)
   count++;
  matrix = new int[count][count];
  String fileName = "C:/Users/gauravy/Desktop/matrix.txt";

  FileInputStream inputStream = new FileInputStream(fileName);
  BufferedReader bf = new BufferedReader(new InputStreamReader(inputStream));

  int lineCount = 0;
  String[] numbers;
  String line = null;
  while ((line = bf.readLine()) != null) {
   numbers = line.split(" ");
   for (int i = 0; i < count; i++) {
    matrix[lineCount][i] = Integer.parseInt(numbers[i]);
   }

   lineCount++;
  }
  bf.close();
  for (int l = 0; l < count; l++)
   for (int s = 0; s < count; s++)
    if (matrix[l][s] == -1) matrix[l][s] = Integer.MAX_VALUE;

  System.out.println("Minimum cost which we evaluated is " + minPath(matrix, 3, count - 1));
 }
 public static int minPath(int[][] mat, int i, int j) {
  int cost;
  if (i == j) return 0;
  else {
   int y = getNodeWithMinDistance(i);
   cost = matrix[i][y] + minPath(mat, y, j);
   if (cost < mat[i][j]) return cost;
   else return mat[i][j];
  }
 }

 public static int getNodeWithMinDistance(int source) {
  int min = matrix[source][source + 1];
  int minNeighbourNode = source + 1;
  for (int k = source + 1; k < count; k++) {
   if (matrix[source][k] < min) {
    min = matrix[source][k];
    minNeighbourNode = k;
   }
  }
  return minNeighbourNode;
 }
}

       
 

No comments:

Post a Comment