Finding paths and shortest paths in a map

I am working on this program that reads a file of metro stations and converts it into a graph. Then it does the following tasks:

• It identifies all the stations belonging on the same line of a given station with the given station as input.

• It finds the shortest path between two stations with the given 2 stations

• In the original the data file metro.txt (The vertices starts after the $. Left integer is starting vertex, middle int is ending vertex, and right integer is weight/Time(s)):

https://drive.google.com/file/d/1ePOoCHmFMi6TNTRPviIucwwUF7gGXy--/view?usp=sharing

• The txt file contains different vertices that can be followed by the same station name when several subway lines pass by the same "physical station" (e.g. Bastille). For each vertex corresponds to a station, and stations with different numbers and the same name are considered as different "stations"

• The line refers to all connected vertices with edges that connects them in cases of -1 weight it is considered as 90 secs constant

However I am getting many bugs. Ex: when 1 is entered for N1: output:

Line: 1 12

Correct output

Line: 1 12 213 235 284 211 86 21 75 142 339 151 13 5 239 27 246 302 366 204 85 351 56 362 256

Here is my code:

import net.datastructures.AdjacencyMapGraph;
import net.datastructures.Edge;
import net.datastructures.Graph;
import net.datastructures.Vertex;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class ParisMetro {
    Graph<String, Integer> sGraph;
    Map<Integer, List<Integer>> lines;
    Map<Vertex<String>, Boolean> visited; // Declaration of visited map

    public ParisMetro(String fileName) throws IOException {
      sGraph = new AdjacencyMapGraph<>(false);
      lines = new HashMap<>();
      read(fileName);
    }

    protected void read(String fileName) throws IOException {
      BufferedReader graphFile = new BufferedReader(new FileReader(fileName));
      String line;
      boolean isWeightSection = false;

      while ((line = graphFile.readLine()) != null) {
        if (line.equals("$")) {
          isWeightSection = true;
          continue;
        }

        StringTokenizer st = new StringTokenizer(line);
        if (isWeightSection && st.countTokens() == 3) {
          String source = st.nextToken();
          String dest = st.nextToken();
          int weight = Integer.parseInt(st.nextToken());
          Vertex<String> sv = sGraph.insertVertex(source);
          Vertex<String> dv = sGraph.insertVertex(dest);
          sGraph.insertEdge(sv, dv, weight);
        } else {
          while (st.hasMoreTokens()) {
            String stationName = st.nextToken();
            if (!stationName.equals("$")) {
              sGraph.insertVertex(stationName);
            }
          }
        }
      }
      graphFile.close();
    }


    public List<String> findShortestPath(String sourceStation, String destinationStation) {
      Map<Vertex<String>, Vertex<String>> previous = new HashMap<>();
      Vertex<String> source = null;
      Vertex<String> destination = null;

      for (Vertex<String> v : sGraph.vertices()) {
        if (v.getElement().equals(sourceStation)) {
          source = v;
        }
        if (v.getElement().equals(destinationStation)) {
          destination = v;
        }
      }

      if (source == null || destination == null) {
        return Collections.emptyList();
      }

      Map<Vertex<String>, Integer> distance = new HashMap<>();
      PriorityQueue<Vertex<String>> queue = new PriorityQueue<>(Comparator.comparingInt(distance::get));

      distance.put(source, 0);
      queue.add(source);

      for (Vertex<String> vertex : sGraph.vertices()) {
        if (!vertex.equals(source)) {
          distance.put(vertex, Integer.MAX_VALUE);
          previous.put(vertex, null);
        }
      }

      while (!queue.isEmpty()) {
        Vertex<String> current = queue.poll();

        for (Edge<Integer> edge : sGraph.outgoingEdges(current)) {
          Vertex<String> neighbor = sGraph.opposite(current, edge);
          int newDistance = distance.get(current) + edge.getElement();
          if (newDistance < distance.get(neighbor)) {
            distance.put(neighbor, newDistance);
            previous.put(neighbor, current);
            queue.add(neighbor);
          }
        }
      }

      List<String> shortestPath = new ArrayList<>();
      Vertex<String> current = destination;
      while (current != null) {
        shortestPath.add(current.getElement());
        current = previous.get(current);
      }
      Collections.reverse(shortestPath);

      return shortestPath;
    }

    public void printDFS(String vert) {
      Vertex<String> vt = getVertex(vert);
      boolean[] visited = new boolean[sGraph.numVertices() + 1]; // Assuming station numbering starts from 1
      List<String> stationsInSameLine = new ArrayList<>();

      if (vt != null) {
        DFS(vt, visited, stationsInSameLine);
      }

      System.out.println("Line: " + String.join(" ", stationsInSameLine));
    }

    private void DFS(Vertex<String> vt, boolean[] visited, List<String> stationsInSameLine) {
      int stationNumber = Integer.parseInt(vt.getElement());
      visited[stationNumber] = true;
      stationsInSameLine.add(vt.getElement());

      for (Edge<Integer> edge : sGraph.outgoingEdges(vt)) {
        Vertex<String> neighbor = sGraph.opposite(vt, edge);
        int neighborStationNumber = Integer.parseInt(neighbor.getElement());
        if (!visited[neighborStationNumber]) {
          DFS(neighbor, visited, stationsInSameLine);
        }
      }
    }

    private Vertex<String> getVertex(String vert) {
      for (Vertex<String> v : sGraph.vertices()) {
        if (v.getElement().equals(vert)) {
          return v;
        }
      }
      return null;
    }

    public static void main(String[] args) {
      if (args.length < 1) {
        System.err.println("Usage: java ParisMetro fileName");
        System.exit(-1);
      }

      try {
        ParisMetro sGraph = new ParisMetro(args[0]);

        // Ask for type of query
        System.out.println("Choose Query Type:");
        System.out.println("1. List stations in the same line (N1)");
        System.out.println("2. Find shortest path between stations (N1, N2)");

        // Read query type
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int queryType = Integer.parseInt(reader.readLine());

        if (queryType == 1) {
          // Query type 1: List stations in the same line for a given station ID (N1)
          System.out.println("Enter Station ID (N1):");
          String stationID = reader.readLine();
          sGraph.printDFS(stationID);
        } else if (queryType == 2) {
          // Query type 2: Find shortest path between stations (N1, N2)
          System.out.println("Enter Start Station ID (N1):");
          String startStationID = reader.readLine();
          System.out.println("Enter Destination Station ID (N2):");
          String destinationStationID = reader.readLine();

          List<String> shortestPath = sGraph.findShortestPath(startStationID, destinationStationID);

          if (shortestPath.isEmpty()) {
            System.out.println("No path found between the stations.");
          } else {
            System.out.println("Shortest Path: " + String.join(" -> ", shortestPath));
          }

          // Update the code based on the algorithm used (e.g., Dijkstra's algorithm)
          System.out.println(sGraph.findShortestPath(startStationID, destinationStationID));
          // The shortestPath method should print the path and time taken
        } else {
          System.out.println("Invalid Query Type");
        }
      } catch (Exception except) {
        System.err.println(except);
        except.printStackTrace();
      }
    }
  }