Question: Using Dijkstra\'s algorithm for computing the shortest path from a des

Question

Question: Using Dijkstra's algorithm for computing the shortest path from a designated vertex (A) to a designated vertex (B) in a directed graph.

assuming a text file with following content:

10
A J 18
A H 79
A I 81
J G 24
J F 76
G F 2
G H 50
F E 4
E D 2
D H 20
H C 50
I D 6
I C 97
I J 27
C B 22

This text file starts with an int which is the number of vertices in the graph. The vertices are assumed to be numbered alphabetically starting with vertex A. Each subsequent line in the text file contains the tail of an edge followed by a space, the head of the edge followed by a space, and the weight of the edge, respectively.

Write a program in c++ or java language which will get this text file as input file, and output the weight of a shortest path from vertex A to vertex B in the graph and the sequence of vertices on a shortest path from 1 A to B.

The resuilt from the above text file is:

142

A-J-G-F-E-D-H-C-B

Explanation / Answer

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package chegg.may;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

/**
*
* @author Sam
*/
public class Dijkstra {
    int n;
    int[][] adj;
    private void findRoute() {
        int[] min = new int[n];
        boolean[] isLocked = new boolean[n];
        int[] parent = new int[n];
        int selected,minCost = 0;
        for (int i = 0; i < n; i++) {
            min[i] = Integer.MAX_VALUE;
            isLocked[i] = false;
            parent[i] = -1;
        }
        System.err.println("TEST");
        min[0] = 0;
        selected = 0;
        while (!isLocked[1] && minCost < Integer.MAX_VALUE) { //untill B is locked
            for (int i = 0; i < n; i ++) //find the updated weights to all neighbours of selected node
                if (adj[selected][i] + min[selected] < min[i] && !isLocked[i]) {
                    min[i] = adj[selected][i] + min[i];
                    parent[i] = selected;
                }
          
            minCost = Integer.MAX_VALUE;
          
            for (int i = 0; i < n; i++) //find next node
                if(min[i] < minCost && !isLocked[i]) {
                    minCost = min[i];
                    selected = i;
                }
            isLocked[selected] = true;
        }
      
        String path = "B";
        selected = 1;
        System.out.println(Arrays.toString(parent));
        while(true) {
            if (parent[selected] == -1)
                break;
            path = (char)('A' + parent[selected]) + "-" + path;
            selected = parent[selected];
        }
      
        System.out.println(min[1]);
        System.out.println(path);
    }
  
    private void readInput(BufferedReader br) throws IOException {
        n = Integer.parseInt(br.readLine());
        adj = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                adj[i][j] = Integer.MAX_VALUE;
        String line;
        while ((line = br.readLine())!=null) {
            char source = line.charAt(0);
            char dest = line.charAt(2);
            int weight = Integer.parseInt(line.substring(4));
            adj[source - 'A'][dest - 'A'] = weight;
        }
    }
  
    public static void main(String[] args) throws IOException {
        Dijkstra dij = new Dijkstra();
        BufferedReader br = new BufferedReader(new FileReader("D:\Prog\Java\data.txt"));
        dij.readInput(br);
        dij.findRoute();
    }
}

I hope this code helps you :)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.