package Assignment;

import java.util.LinkedList;
import java.util.ArrayList;

public class Shortestpath {

    public double distance = 0;

    // Dijkstra's algorithm to find shortest path from s to all other nodes
    public int[] dijkstra(Graph G, int s) {
        final double[] dist = new double[G.id];  // shortest known distance from "s"
        final int[] pred = new int[G.id];  // preceeding node in path
        final boolean[] visited = new boolean[G.id]; // all false initially

        //Set all dist to Infinity
        for (int i = 0; i < dist.length; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        //Except source =0
        dist[s] = 0;

        for (int i = 0; i < dist.length; i++) {
            final int next = minVertex(dist, visited);
            visited[next] = true;

            // The shortest path to next is dist[next] and via pred[next].

            final int[] n = new int[G.get_adjacent(G.get_vertex(next)).size()];// <<<< Buggg
            // n = set of vertex id that connect with next
            LinkedList<Vertex> temp = (LinkedList) G.get_adjacent(G.get_vertex(next));//get in type of linkedlist<vertex>
            for (int k = 0; k < temp.size(); k++) {
                n[k] = temp.get(k).get_id();  //insert id = vertex from linkedlist
            }
            for (int j = 0; j < n.length; j++) {
                final int v = n[j];
                int d;
                if (G.get_edge(G.get_vertex(next), G.get_vertex(v)) == null) {
                    d = (int) (dist[next]);
                } else {
                    d = (int) (dist[next] + G.get_edge(G.get_vertex(next), G.get_vertex(v)).get_distance());
                }
                if (dist[v] > d) {
                    dist[v] = d;
                    pred[v] = next;
                }
            }
        }
        return pred;  // (ignore pred[s]==0!)
    }

    private static int minVertex(double[] dist, boolean[] v) {
        double x = Integer.MAX_VALUE;
        int y = -1;   // graph not connected, or no unvisited vertices
        for (int i = 0; i < dist.length; i++) {
            if (!v[i] && dist[i] < x) {
                y = i;
                x = dist[i];
            }
        }
        return y;
    }

    public ArrayList<Vertex> printPath(Graph G, int[] pred, int s, int e) {
        ArrayList<Vertex> path = new ArrayList<Vertex>();
        int x = e, i = 0;
        while (x != s) {
            path.add(0, G.get_vertex(x));
            x = pred[x];
        }
        path.add(0, G.get_vertex(s));
        for (i = 0; i < path.size() - 1; i++) {
            distance += G.get_edge(path.get(i), path.get(i + 1)).get_distance();
        }
        i = 0;
        return path;
    }
}