import java.io.*;

// Dijkstra-algoritmen for å løse Single Source Shortest Path problemet
//
// Bruker en enkel vektet graf med kantlengdematrise, der data i
// nodene bare er en tekststreng (superklassen enkelVektetGraf)
//
// O(n*log(n))-versjon som bruker en min-heap til å lagre graf-nodene
//
public class dijkstra3 extends enkelVektetGraf
{
    // Konstruktør, leser inn en graf fra fil
    //
    public dijkstra3(String filNavn)
    {
	super(filNavn);
    }
 
    // O(n*log(n)) Dijkstra-algoritme for SSSP med start i en node S
    // Skriver ut løsningsarrayen
    //
    public void dijkstraSSSP(int S)
    {
	// Array for å merke av noder som vi allerede har funnet
	// korteste vei til fra S
	boolean funnet[] = new boolean[n];

	// Array for å lagre hittil korteste kjente avstand til hver
	// node fra S
	int avstand[] = new int[n];

	// Heap som brukes for å finne noden med minst avstand effektivt
	nodeHeap nH = new nodeHeap(n);

	// Initierer de to hjelpe-arrayene og heapen
	for (int i = 0; i < n; i++)
	{
	    avstand[i] = (i == S ? 0 : UENDELIG);
	    funnet[i] = false;
	    nH.insert(i, avstand[i]);
	}

	// Nåværende node og antall noder som er funnet
	int denne = S, antall = 0;

	while (antall < n)
	{
	    // Finn noden med minste avstand fra S som ennå ikke er funnet
	    denne = nH.removeMin();

	    // Oppdater avstander for alle naboer til nåværende node
	    // som ikke er funnet
	    for (int i = 0; i < n; i++)
		if (!funnet[i])
		{
		    int l = avstand[denne] + lengde[denne][i];
		    if (l < avstand[i])
		    {
			// Funnet kortere avstand til node nummer i
			avstand[i] = l;

			// Må også justerere heapen med ny avstandsverdi
			nH.adjust(i, avstand[i]);
		    }
		}

	    // Marker at vi har funnet korteste avstand til nåværende node
	    funnet[denne] = true;
	    antall++;
	}

	// Skriver ut løsningen
	System.out.printf("%2s ", data[S]);
	for (int i = 0; i < n; i++)
	    if (avstand[i] == UENDELIG)
		System.out.printf(" * ", avstand[i]);
	    else
		System.out.printf("%2d ", avstand[i]);
	System.out.println();
    }

    // Testprogram
    //
    public static void main(String args[])
    {
	// Leser navnet på en fil med grafdata som input fra
	// kommandolinjen
	String filNavn = " ";
	try
	{
	     if (args.length != 1)
		 throw new IOException("Mangler filnavn");
	     filNavn = args[0];
       	}
        catch (Exception e)
	{
	     System.err.println(e);
	     System.exit(1);
	}

	// Oppretter ny graf
	dijkstra3 G = new dijkstra3(filNavn);

	// Skriver ut kantlengdematrisen før Dijkstra
	System.out.println("Graf:");
	G.skriv();

	// Kjører Dijkstra en gang med start i hver node og skriver ut
	// løsningen
	System.out.println("\nDijkstra:");
	G.skrivHeader();
	for (int S = 0; S < G.antallNoder(); S++)
	    G.dijkstraSSSP(S);
    }
}