Objective: Work with Dijkstra\'s single-source shortest path algorithm. Overview

Question

Objective:

    Work with Dijkstra's single-source shortest path algorithm.


Overview:

    In this project you will use Dijkstra's algorithm to find route information between two airports
    chosen by the user. The user will be shown a route that results in the lowest price.


Details:

    Create a class called Dijkstra.

    The structure of this class in terms of inner classes and methods will be up to you.
    Points will be reduced if your program is not well organized and commented.

    Basic requirements are:

      1) Input a file airports.txt that contains the graph in adjacency list form.
      2) Performs the Dijkstra algorithm on the graph to create shortest path information.
      3) Prints the shortest path information between two airports chosen by the user.
      4) Repeats until the user chooses to exit.

    Notice that in this case "shortest" means "cheapest".  

    You are expected to write Dijkstra's algorithm yourself following the pseudocode found in both the
    slides and in the textbook. You can use the Vertex class and printPath method found in the textbook.
    You may not use code for Dijkstra's algorithm found from other sources.

    Your output should match the sample output below:

    Sample output:

    Enter departure airport: DFW
    Enter arrival airport:    SFO

    Price:       1100
    Connections: 1
    Route:       DFW -> LAX -> SFO

    Check another route (Y/N)?

Here is Airports.txt

Explanation / Answer

import java.util.*;

public class Dijkstra

{

public  int distance[] = new int[10];

public  int cost[][] = new int[10][10];

public void calc(int n,int s)

{

  int flag[] = new int[n+1];

  int i,minpos=1,k,c,minimum;

for(i=1;i<=n;i++)

  {

flag[i]=0;t

his.distance[i]=this.cost[s][i];

}

c=2;

  while(c<=n)

  {

   minimum=99;

   for(k=1;k<=n;k++)

   {

          if(this.distance[k]<minimum && flag[k]!=1)

       {

        minimum=this.distance[i];

        minpos=k;

       }

      }

            flag[minpos]=1;

      c++;

      for(k=1;k<=n;k++)

{

         if(this.distance[minpos]+this.cost[minpos][k] <  this.distance[k] && flag[k]!=1 )

    this.distance[k]=this.distance[minpos]+this.cost[minpos][k];

}  

  }

}

public static void main(String args[])

{

  int nodes,source,i,j;

  Scanner in = new Scanner(System.in);

  System.out.println("Enter the Number of Nodes ");

  nodes = in.nextInt();

  Dijkstra d = new Dijkstra();

  System.out.println("Enter the Cost Matrix Weights: ");

        for(i=1;i<=nodes;i++)

          for(j=1;j<=nodes;j++)

    {

            d.cost[i][j]=in.nextInt();

            if(d.cost[i][j]==0)

              d.cost[i][j]=999;

          }

  System.out.println("Enter the Source Vertex : ");

  source=in.nextInt();

     d.calc(nodes,source);

  System.out.println("The Shortest Path from Source "+source+" to all other vertices are : ");

        for(i=1;i<=nodes;i++)

          if(i!=source)

System.out.println("source :"+source+" destination :"+i+" MinCost is :"+d.distance[i]+" ");

}

}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

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