Using JAVA: lmplement from the user: first: must take input from the keyboard "please enter the vertices"then you enter a list of cities. Then you provide a list of vertices. For each city the program should prompt a pair adjacent vertices including for sacramento.you can tokenizer the string for each city. Second input:please enter the adjacent vrtice for v1, v2,v3 ..then run for each v1,v2 ,v3 . Third input "please enter the source "by initialize the start and end of the source , As Output: 1) "The shortest path is:" example: Sacramento,SFO,LA,Vegas,Dallas,NY. where Cost is:" Program run again enter "next "result from other cities enter already as Input by the user. Keep the the program path after you finish.

import java.util.PriorityQueue;

import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Scanner;

import java.util.Arrays;

class Vertex implements Comparable

{

//Scanner scan = new Scanner(System.in);

public final String name;

public Edge[] adjacencies;

public double minDistance = Double.POSITIVE_INFINITY;

public Vertex previous;

public Vertex(String argName) { name = argName; }

public String toString() { return name; }

public int compareTo(Vertex other)

{

return Double.compare(minDistance, other.minDistance);

}

}

class Edge

{

public final Vertex target;

public final double weight;

public Edge(Vertex argTarget, double argWeight)

{ target = argTarget; weight = argWeight; }

}

public class DijKstra

{

public static void computePaths(Vertex source)

{

source.minDistance = 0.;

PriorityQueue vertexQueue = new PriorityQueue();

vertexQueue.add(source);

while (!vertexQueue.isEmpty()) {

Vertex u = vertexQueue.poll();

//Visit each edge exiting u

for (Edge e : u.adjacencies)

{

Vertex v = e.target;

double weight = e.weight;

double distanceThroughU = u.minDistance + weight;

if (distanceThroughU < v.minDistance) {

vertexQueue.remove(v);

v.minDistance = distanceThroughU ;

v.previous = u;

vertexQueue.add(v);

}

}

}

}

public static List getShortestPathTo(Vertex target)

{

List path = new ArrayList();

for (Vertex vertex = target; vertex != null; vertex = vertex.previous)

path.add(vertex);

Collections.reverse(path);

return path;

}

public static void main(String[] args) {

//Scanner scan = new Scanner(System.in);

// System.out.println("steps ");

Vertex Sacramento = new Vertex("Sacramento");

Vertex SFO = new Vertex("SFO");

Vertex LA = new Vertex("LA");

Vertex Vegas = new Vertex("Vegas");

Vertex Dallas = new Vertex("Dallas");

Vertex NY = new Vertex("NY");

Vertex Boston = new Vertex("Boston");

Vertex NJ = new Vertex("NJ");

Vertex Atlanta = new Vertex("Atlanta");

Vertex Detroit = new Vertex("Detroit");

Vertex Miami = new Vertex("Miami");

Vertex Chicago = new Vertex ("Chicago");

Vertex DC = new Vertex ("DC");

//System.out.println ("Please,enter the Adjacencies");

Sacramento.adjacencies = new Edge[]{ new Edge(Atlanta,35)};

Sacramento.adjacencies = new Edge[]{ new Edge(SFO,50)};

SFO.adjacencies = new Edge[]{ new Edge(LA, 60) };

SFO.adjacencies = new Edge[] { new Edge(Chicago,35)};

SFO.adjacencies = new Edge[] { new Edge(Detroit,70)};

LA.adjacencies = new Edge[]{ new Edge(Vegas,30)};

Chicago.adjacencies = new Edge[] { new Edge(Vegas,5)};

Chicago.adjacencies = new Edge[] { new Edge (Miami,50)};

Atlanta.adjacencies = new Edge[] { new Edge (Detroit,20)};

Atlanta.adjacencies= new Edge[] { new Edge (NJ,45)};

Atlanta.adjacencies= new Edge[] { new Edge (Chicago,60)};

NJ.adjacencies= new Edge[] { new Edge (Miami,30)};

NJ.adjacencies= new Edge[] { new Edge (Boston,25)};

Miami.adjacencies= new Edge[] { new Edge (DC,50)};

DC.adjacencies= new Edge[] { new Edge (NY,15)};

Detroit.adjacencies= new Edge[]{ new Edge (Chicago,10)};

Vegas.adjacencies = new Edge[]{ new Edge(Dallas,20) };

Dallas.adjacencies = new Edge[]{ new Edge(NY, 10) };

//System.out.println ("Please, enter the Source");

computePaths(Sacramento); // run Dijkstra

System.out.println("Cost " + NY + ": " + NY.minDistance);

List path = getShortestPathTo(NY);

System.out.println("Path: " + path);

}

}