Кратчайшие пути из матрицы смежности ⇐ JAVA

[Anonymous]

Я работаю над проектом, в котором создаю матрицу смежности городов, и мне нужно найти и распечатать до трех кратчайших путей между двумя городами на основе времени или стоимости. Я изо всех сил пытаюсь понять, какой самый простой способ сделать это. Я должен использовать очередь приоритетов для хранения кратчайших путей. Если у кого-нибудь есть идеи или он может показать мне, как это сделать, было бы здорово. Спасибо.

Код: Выделить всё

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
import java.util.Scanner;
import java.util.LinkedList;

class Destination{
String name;
double cost;
double time;

public String getName(){
return name;
}
}
class City{
String name;
LinkedList reachableCities = new LinkedList();

public void addReachableCity(String destinationName, double cost, double time){
boolean duplicate = false;
for(Destination element : reachableCities){
if(element.getName().equals(destinationName)){
duplicate = true;
}
}

if(duplicate == false){
Destination destination = new Destination();
destination.name = destinationName;
destination.cost = cost;
destination.time = time;

reachableCities.add(destination);
}
}

public String getName(){
return name;
}

public LinkedList getDestinations(){
return reachableCities;
}
}

public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
System.out.println("Enter flight data input file: ");
String flightData = scanner.nextLine();
LinkedList cities = createList(flightData);

System.out.println("Enter requested flight plans input file: ");
String requestdFlights = scanner.nextLine();

printList(cities);
}

public static void findPaths(LinkedList cities, String fileName){
int numLines = 0;
String line;
String startCity = "";
String destinationCity = "";
String timeOrCost = "";
try{
Scanner scanner = new Scanner(file);
numLines = Integer.parseInt(scanner.nextLine());
for(int i = 0; i < numLines; i++){
line = scanner.nextLine();
int pipedCounter = 0;
for(int j = 0; j < line.length(); j++){
if(pipedCounter == 0 && line.charAt(j) != '|'){
startCity += line.charAt(j);
}
else if(pipedCounter == 1 && line.charAt(j) != '|'){
destinationCity += line.charAt(j);
}
else if(pipedCounter == 2 && line.charAt(j) != '|'){
timeOrCost += line.charAt(j);
}
else{
pipedCounter++;
}
}

if(timeOrCost.equals("T")){
for(City element : cities){
if(element.equals(startCity)){
findPathTimes(element, destinationCity);
}
}
}
}
}
}

public static void findPathTimes(City element, String destinationCity){
//
}
public static void printList(LinkedList list){
for(City element : list){
LinkedList destinations = element.getDestinations();
System.out.println(element.getName());
for(Destination destination: destinations){
System.out.println(destination.getName());
}
System.out.println();
}
}

public static LinkedList createList(String fileName) {
String line;
String cityName = "";
String destinationName = "";
String cost = "";
String time = "";
int numLines = 0;
LinkedList cities = new LinkedList();
File file = new File(fileName);
try {
Scanner scanner = new Scanner(file);
numLines = Integer.parseInt(scanner.nextLine());
for(int i = 0; i < numLines; i++){
line = scanner.nextLine();
int pipedCounter = 0;
for(int j = 0; j < line.length();  j++){
if(pipedCounter == 0 && line.charAt(j) != '|'){
cityName += line.charAt(j);
}
else if(pipedCounter == 1 && line.charAt(j) != '|'){
destinationName += line.charAt(j);
}
else if(pipedCounter == 2 && line.charAt(j) != '|'){
cost += line.charAt(j);
}
else if(pipedCounter == 3 && line.charAt(j) != '|'){
time += line.charAt(j);
}
else{
pipedCounter++;
}
}

boolean duplicate = false;
for(City element : cities){
if(element.getName().equals(cityName)){
duplicate = true;
element.addReachableCity(destinationName, Double.parseDouble(cost), Double.parseDouble(time));
}
}

if(duplicate == false){
City city = new City();
city.name = cityName;
city.addReachableCity(destinationName, Double.parseDouble(cost), Double.parseDouble(time));
cities.add(city);
}

duplicate = false;
for(City element : cities){
if(element.getName().equals(destinationName)){
duplicate = true;
element.addReachableCity(cityName, Double.parseDouble(cost), Double.parseDouble(time));
}
}

if(duplicate == false){
City destination = new City();
destination.name = destinationName;
destination.addReachableCity(cityName, Double.parseDouble(cost), Double.parseDouble(time));
cities.add(destination);
}

cityName = "";
destinationName = "";
cost = "";
time = "";
}
} catch (FileNotFoundException e) {
System.err.println("File not found: " + fileName);
return null;
}
return cities;
}
}

Честно говоря, я создал матрицу смежности и с тех пор потерялся. Я изучил поиск в ширину, чтобы найти кратчайший путь, но не могу понять, как его реализовать.

Подробнее здесь: https://stackoverflow.com/questions/783 ... ncy-matrix