Oppgave 2

  // ny versjon
  public String veiTil(String node)  // returnerer veien i rett rekkefølge
  {
    Node p = noder.get(node);
    if (p == null) throw new IllegalArgumentException(node + " er ukjent!");
    if (p.forrige == null) return "[], 0";  // ingen vei til p

    Deque<String> stakk = new ArrayDeque<>(); // bruker en deque som stakk
    int noder = -1;

    while (p != null)
    {
      stakk.push(p.navn);                 // legger nodenavnet på stakken
      p = p.forrige;                      // går til forrige node på veien
      noder++;                            // en node til på veien
    }

    return stakk.toString() + ", " + noder;
  }

  public static void main(String... args) throws IOException
  {
    String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap11/1/graf3.txt";
    Graf graf = new Graf(url);

    String startnode = "A";
    graf.kortestVeiFra(startnode);

    String[] noder = graf.nodenavn();  // alle nodene

    for (String node : noder)
    {
      System.out.println("Kortest vei fra " + startnode + " til "
                       + node + ": " + graf.veiTil(node));
    }
  }
  /*
  Kortest vei fra A til A: [], 0
  Kortest vei fra A til B: [A, B], 1
  Kortest vei fra A til C: [A, B, C], 2
  Kortest vei fra A til D: [A, D], 1
  Kortest vei fra A til E: [A, E], 1
  Kortest vei fra A til F: [A, E, F], 2
  Kortest vei fra A til G: [A, D, G], 2
  Kortest vei fra A til H: [A, E, H], 2
  Kortest vei fra A til I: [A, E, I], 2
  Kortest vei fra A til J: [A, D, G, J], 3
  Kortest vei fra A til K: [A, D, G, K], 3
  Kortest vei fra A til L: [A, E, I, L], 3
  Kortest vei fra A til M: [A, D, G, J, M], 4
  Kortest vei fra A til N: [A, D, G, K, N], 4
  Kortest vei fra A til O: [A, D, G, K, O], 4  
  */

Oppgave 3

     Kortest vei fra A til A: [], 0
     Kortest vei fra A til B: [A, B], 1
     Kortest vei fra A til C: [A, C], 1
     Kortest vei fra A til D: [A, B, D], 2
     Kortest vei fra A til E: [A, B, D, E], 3
     Kortest vei fra A til F: [A, B, D, F], 3
     Kortest vei fra A til G: [A, B, H, G], 3
     Kortest vei fra A til H: [A, B, H], 2
     Kortest vei fra A til I: [A, C, I], 2
     Kortest vei fra A til J: [A, B, H, J], 3
     

Oppgave 4

  public String kortestVei(String franode, String tilnode)
  {
    Node p = noder.get(franode);               // henter franoden
    if (p == null) throw new IllegalArgumentException(franode + " er ukjent!");

    Node q = noder.get(tilnode);               // henter tilnoden
    if (q == null) throw new IllegalArgumentException(tilnode + " er ukjent!");

    Queue<Node> kø = new ArrayDeque<>();       // oppretter en kø
    p.besøkt = true;                           // p er den første vi besøker
    kø.offer(p);                               // legger p i køen

    while (!kø.isEmpty())                      // så lenge køen ikke er tom
    {
      p = kø.poll();                           // tar ut en node fra køen
      if (p == q) break;                       // vi har funnet tilnode

      for (Node r : p.kanter)                  // kantene fra p
      {
        if (!r.besøkt)                         // denne er ikke besøkt
        {
          r.besøkt = true;                     // nå er den besøkt
          r.forrige = p;                       // vi kom dit fra p
          kø.offer(r);                         // legger noden i køen
        }
      }
    }
    if (p != q) return "[], 0";                // ingen vei 

    Deque<String> stakk = new ArrayDeque<>();  // bruker en deque som stakk
    int noder = -1;

    while (p != null)
    {
      stakk.push(p.navn);           // legger nodenavnet på stakken
      p = p.forrige;                // går til forrige node på veien
      noder++;                      // en node til på veien
    }

    return stakk.toString() + ", " + noder;
  }

Oppgave 5

Hver node i klassen Graf har referansen forrige og den brukes til å gi oss den korteste veien fra noden tilbake til startnoden. I MGraf kan vi få til samme effekt ved hjelp av en hjelpetabell. MGraf har allerede en tabellreferanse forrige, men tabellen er i utgangspunktet ikke opprettet. I dette tilfellet er det ikke mulig å ha tabellen som en lokal tabell i metoden kortesteVeiFra() siden vi trenger å aksessere den etter at metoden har gjort seg ferdig. I MGraf trenger vi heller ikke en nullstill-metode siden tabellene besøkt og forrige blir opprettet på nytt hver gang.

  public void kortestVeiFra(String node)
  {
    int is = finn(node);    // indeks i den sorterte navnetabellen
    if (is < 0) throw new IllegalArgumentException(node + " er ukjent!");
    int i = indeks[is];     // indeks i den usorterte navnetabellen

    boolean[] besøkt = new boolean[antall];    // hjelpetabell
    forrige = new int[antall];                 // hjelpetabell
    Arrays.fill(forrige, -1);                  // fyller med -1

    Queue<Integer> kø = new ArrayDeque<>();    // oppretter en kø
    besøkt[i] = true;                          // node i er den første vi besøker
    kø.offer(i);                               // legger i i køen

    while (!kø.isEmpty())                      // så lenge køen ikke er tom
    {
      i = kø.poll();                           // tar ut en node fra køen

      for (int j = 0; j < antall; j++)         // nodene det går en kant til
      {
        if (graf[i][j] && !besøkt[j])          // denne er ikke besøkt
        {
          besøkt[j] = true;                    // nå er den besøkt
          forrige[j] = i;                      // veien går fra i til j
          kø.offer(j);                         // legger noden i køen
        }
      }
    }
  }

  public String veiTil(String node)
  {
    int is = finn(node);  // indeks i den sorterte navnetabellen
    if (is < 0) throw new IllegalArgumentException(node + " er ukjent!");
    int i = indeks[is];   // indeks i den usorterte navnetabellen
    if (forrige[i] == -1) return "[], 0";  // ingen vei til denne noden

    Deque<String> stakk = new ArrayDeque<>();  // bruker en deque som stakk
    int noder = -1;
    while (i != -1)
    {
      stakk.push(navn[i]);                 // legger nodenavnet på stakken
      i = forrige[i];                      // går til forrige node på veien
      noder++;
    }

    return stakk.toString() + ", " + noder;
  }