public class Roadmap extends Graph {

    // Determines and prints the shortest path from station "from" to station "to" (-> vertex array indices). The shortest distance is returned.
    public int printShortestDistance(int from, int to) {
        return dijkstra(from, to)[to];
    }


    // Determines the shortest paths from station "from" (-> vertex array index) to all stations and returns them in an array.
    public int[] printShortestDistances(int from) {
        return dijkstra(from, vCount - 1);
    }


    private int[] dijkstra(int from, int to) {
        boolean[] visited = new boolean[vCount];
        int[] distance = new int[vCount];
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < vCount; i++) {
            distance[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }
        distance[from] = 0;

        for (int i = 0; i < vCount - 1; i++) {
            int min = Integer.MAX_VALUE;
            int min_index = -1;
            for (int j = 0; j < vCount; j++) {
                if (!visited[j] && distance[j] <= min) {
                    min = distance[j];
                    min_index = j;
                }
            }
            visited[min_index] = true;

            for (int j = 0; j < vCount; j++) {
                if (!visited[j] && getWeight(min_index, j) != 0 && distance[min_index] + getWeight(min_index, j) < distance[j]) {
                    distance[j] = distance[min_index] + getWeight(min_index, j);
                    sb.append("\n over ").append(vertices[j].toString()).append(" ").append(distance[j]);
                }
            }
        }

        for (int j = 0; j < vCount; j++) {
            if (distance[j] == Integer.MAX_VALUE) {
                distance[j] = -1;
            }
        }
        System.out.print("Shortest distance from " + vertices[from] + " to " + vertices[to] + " is: " + distance[to]);
        System.out.println(sb.toString());
        return distance;
    }

    private int getWeight(int v1, int v2) {
        for (int i = 0; i < eCount; i++) {
            if (edges[i].in == v1 && edges[i].out == v2 || edges[i].in == v2 && edges[i].out == v1)
                return edges[i].weight;
        }
        return 0;
    }
}