Oppgave 1

Koden

  String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap11/2/vgraf1.txt";
  VGraf vgraf = new VGraf(url);

  String nodenavn = "A";
  vgraf.kortestVeiFra(nodenavn);

  for (String n: vgraf)
  {
    System.out.println(
      "Korteste vei fra " + nodenavn + " til " +
      n + ": " + vgraf.veiTil(n) + " lengde: " + vgraf.avstand(n));
  }

vil gi flg. utskrift:

  Korteste vei fra A til A: [A] lengde: 0
  Korteste vei fra A til B: [A, B] lengde: 2
  Korteste vei fra A til C: [A, C] lengde: 3
  Korteste vei fra A til D: [A, B, D] lengde: 4
  Korteste vei fra A til E: [A, B, E] lengde: 6
  Korteste vei fra A til F: [A, C, F] lengde: 6
  Korteste vei fra A til G: [A, C, F, G] lengde: 8

Vi får nøyaktig samme utskrift med vgraf2.txt istedenfor vgraf1.txt.

Oppgave 2

I første del av while-løkken i Programkode 11.2.3 a) letes det i den usorterte tabellen aktiv (en ArrayList) etter noden med minst avstandsverdi. Deretter tas den ut (remove). Men det å fjerne en node inne i en tabell er kostbart. Da må resten av nodene forskyves én enhet mot venstre. En bedre løsning er å ta vare på noden i posisjon m (vha. get), så flytte den siste noden i tabellen til posisjon m (vha. set og get) og så fjerne den siste (remove). F.eks. slik:

  Node denne = aktiv.get(m);              // noden med minst avstand
  int sist = aktiv.size() - 1;            // indeks til siste node
  aktiv.set(m, aktiv.get(sist));          // flytter den siste til m
  aktiv.remove(sist);                     // fjerner den siste
  denne.ferdig = true;                    // denne er tatt ut

Oppgave 3

Hvis en bruker vgraf3.txt i koden i Oppgave 1, kommer denne utskriften:

  Korteste vei fra A til A: [A] lengde: 0
  Korteste vei fra A til B: [A, B] lengde: 4
  Korteste vei fra A til C: [A, B, C] lengde: 8
  Korteste vei fra A til D: [A, F, D] lengde: 4
  Korteste vei fra A til E: [A, B, E] lengde: 7
  Korteste vei fra A til F: [A, F] lengde: 3
  Korteste vei fra A til G: [A, F, D, G] lengde: 7
  Korteste vei fra A til H: [A, B, E, H] lengde: 9
  Korteste vei fra A til I: [A, F, I] lengde: 4
  Korteste vei fra A til J: [A, F, I, L, J] lengde: 8
  Korteste vei fra A til K: [K] lengde: 2147483647
  Korteste vei fra A til L: [A, F, I, L] lengde: 7
  Korteste vei fra A til M: [A, F, I, N, Q, O, M] lengde: 11
  Korteste vei fra A til N: [A, F, I, N] lengde: 6
  Korteste vei fra A til O: [A, F, I, N, Q, O] lengde: 10
  Korteste vei fra A til P: [P] lengde: 2147483647
  Korteste vei fra A til Q: [A, F, I, N, Q] lengde: 9
  Korteste vei fra A til R: [A, F, I, N, Q, O, M, R] lengde: 14

Obs: Når det står lengde 2147483647 betyr det at det ikke finnes noen vei til den noden.

For å bruke Programkode 11.2.3 c) til å finne korteste vei i VGraf63, må du i koden bruke vgraf63.txt, "0" som fra og "62" som til. Da vil du få denne utskriften hvis du bruker den versjonen av kortestVeiFra() som står i Programkode 11.2.3 a):

  Utskrift: Vei fra 0 til 62: [0, 2, 7, 14, 22, 32, 41, 49, 56, 60, 62], 18

Hvis du isteden bruker koden fra Oppgave 1 med 0 som startnode, kommer denne utskriften:

  Korteste vei fra 0 til 0: [0] lengde: 0
  Korteste vei fra 0 til 1: [0, 1] lengde: 3
  Korteste vei fra 0 til 10: [0, 1, 4, 10] lengde: 8
  Korteste vei fra 0 til 11: [0, 1, 4, 11] lengde: 7
  Korteste vei fra 0 til 12: [0, 2, 6, 12] lengde: 9
  Korteste vei fra 0 til 13: [0, 2, 7, 13] lengde: 8
  Korteste vei fra 0 til 14: [0, 2, 7, 14] lengde: 7
  Korteste vei fra 0 til 15: [0, 3, 8, 15] lengde: 7
  Korteste vei fra 0 til 16: [0, 3, 8, 16] lengde: 9
  Korteste vei fra 0 til 17: [0, 3, 9, 17] lengde: 9
  Korteste vei fra 0 til 18: [0, 1, 4, 10, 18] lengde: 9
  Korteste vei fra 0 til 19: [0, 1, 4, 11, 19] lengde: 9
  Korteste vei fra 0 til 2: [0, 2] lengde: 2
  Korteste vei fra 0 til 20: [0, 1, 4, 11, 20] lengde: 10
  Korteste vei fra 0 til 21: [0, 2, 7, 13, 21] lengde: 10
  Korteste vei fra 0 til 22: [0, 2, 7, 14, 22] lengde: 9
  Korteste vei fra 0 til 23: [0, 3, 8, 15, 23] lengde: 10
  Korteste vei fra 0 til 24: [0, 3, 8, 15, 24] lengde: 9
  Korteste vei fra 0 til 25: [0, 3, 8, 16, 25] lengde: 10
  Korteste vei fra 0 til 26: [0, 3, 9, 17, 26] lengde: 10
  Korteste vei fra 0 til 27: [0, 1, 4, 10, 18, 27] lengde: 11
  Korteste vei fra 0 til 28: [0, 1, 4, 11, 19, 28] lengde: 10
  Korteste vei fra 0 til 29: [0, 1, 4, 11, 19, 29] lengde: 11
  Korteste vei fra 0 til 3: [0, 3] lengde: 4
  Korteste vei fra 0 til 30: [0, 2, 7, 13, 21, 30] lengde: 13
  Korteste vei fra 0 til 31: [0, 2, 7, 14, 22, 31] lengde: 10
  Korteste vei fra 0 til 32: [0, 2, 7, 14, 22, 32] lengde: 11
  Korteste vei fra 0 til 33: [0, 3, 8, 15, 24, 33] lengde: 10
  Korteste vei fra 0 til 34: [0, 3, 8, 16, 25, 34] lengde: 12
  Korteste vei fra 0 til 35: [0, 3, 9, 17, 26, 35] lengde: 11
  Korteste vei fra 0 til 36: [0, 1, 4, 10, 18, 27, 36] lengde: 14
  Korteste vei fra 0 til 37: [0, 1, 4, 10, 18, 37] lengde: 13
  Korteste vei fra 0 til 38: [0, 1, 4, 11, 19, 28, 38] lengde: 12
  Korteste vei fra 0 til 39: [0, 1, 4, 11, 19, 29, 39] lengde: 14
  Korteste vei fra 0 til 4: [0, 1, 4] lengde: 6
  Korteste vei fra 0 til 40: [0, 2, 7, 14, 22, 31, 40] lengde: 12
  Korteste vei fra 0 til 41: [0, 2, 7, 14, 22, 32, 41] lengde: 12
  Korteste vei fra 0 til 42: [0, 3, 8, 15, 24, 33, 42] lengde: 11
  Korteste vei fra 0 til 43: [0, 3, 8, 16, 25, 34, 43] lengde: 13
  Korteste vei fra 0 til 44: [0, 3, 9, 17, 26, 35, 44] lengde: 13
  Korteste vei fra 0 til 45: [0, 1, 4, 10, 18, 37, 45] lengde: 14
  Korteste vei fra 0 til 46: [0, 1, 4, 11, 19, 28, 38, 46] lengde: 14
  Korteste vei fra 0 til 47: [0, 1, 4, 11, 19, 28, 38, 47] lengde: 13
  Korteste vei fra 0 til 48: [0, 2, 7, 14, 22, 31, 40, 48] lengde: 13
  Korteste vei fra 0 til 49: [0, 2, 7, 14, 22, 32, 41, 49] lengde: 13
  Korteste vei fra 0 til 5: [0, 1, 5] lengde: 7
  Korteste vei fra 0 til 50: [0, 3, 8, 15, 24, 33, 42, 50] lengde: 13
  Korteste vei fra 0 til 51: [0, 3, 8, 16, 25, 34, 43, 51] lengde: 15
  Korteste vei fra 0 til 52: [0, 3, 9, 17, 26, 35, 44, 52] lengde: 15
  Korteste vei fra 0 til 53: [0, 1, 4, 11, 19, 28, 38, 46, 53] lengde: 15
  Korteste vei fra 0 til 54: [0, 1, 4, 11, 19, 28, 38, 47, 54] lengde: 15
  Korteste vei fra 0 til 55: [0, 2, 7, 14, 22, 31, 40, 48, 55] lengde: 15
  Korteste vei fra 0 til 56: [0, 2, 7, 14, 22, 32, 41, 49, 56] lengde: 14
  Korteste vei fra 0 til 57: [0, 3, 8, 15, 24, 33, 42, 50, 57] lengde: 15
  Korteste vei fra 0 til 58: [0, 3, 8, 16, 25, 34, 43, 51, 58] lengde: 16
  Korteste vei fra 0 til 59: [0, 1, 4, 11, 19, 28, 38, 47, 54, 59] lengde: 16
  Korteste vei fra 0 til 6: [0, 2, 6] lengde: 5
  Korteste vei fra 0 til 60: [0, 2, 7, 14, 22, 32, 41, 49, 56, 60] lengde: 16
  Korteste vei fra 0 til 61: [0, 3, 8, 15, 24, 33, 42, 50, 57, 61] lengde: 16
  Korteste vei fra 0 til 62: [0, 2, 7, 14, 22, 32, 41, 49, 56, 60, 62] lengde: 18
  Korteste vei fra 0 til 7: [0, 2, 7] lengde: 4
  Korteste vei fra 0 til 8: [0, 3, 8] lengde: 5
  Korteste vei fra 0 til 9: [0, 3, 9] lengde: 7

Oppgave 4

I VGraf63 vil korteste vei mellom 0 og 62, som vi har sett i Oppgave 2, ha lengde 18. Men det er flere korteste veier mellom de to nodene. Faktisk fem forskjellige. Se Oppgave 4. I Oppgave 2 fant vi at den første versjonen av kortestVeiFra() gav veien [0, 2, 7, 14, 22, 32, 41, 49, 56, 60, 62]. Hvis vi isteden bruker den forbedrede versjonen fra Programkode 11.2.3 d), får vi veien [0, 3, 8, 15, 24, 33, 42, 50, 57, 61, 62]. Sjekk i VGraf63 at begge veiene har lengde 18. I algoritmen leter vi etter noden med minst avstandsverdi. Men det er datastrukturen som bestemmer i hvilken rekkefølge de med samme avstandsverdi ligger. I den første versjonen ligger de fortløpende i listen. Men i den andre der vi bruker en heapbasert prioritetskø, kan de ligge annerledes. Derfor, når det er flere noder med minst avstandsverdi, vil det i de to versjonene kunne velges forskjellige noder.

Oppgave 5

Det er bare å legge inn en utskriftssetning som første setning i while (!aktiv.isEmpty()). som skriver ut aktiv.size(). I tilfellet med en liste inneholder den maks 12 noder og med binærheap maks 16 instanser av klassen Avstand. I gjennomsnitt blir det hhv. 8,4 og 11,2.

Oppgave 6

Generelt kan det være flere korteste veier mellom to noder i en vektet graf. I VGraf63 har korteste vei mellom 0 og 62 lengde 18 og det er fem forskjellige veier som har denne lengden. I Dijkstras algoritme settes referansen forrige i hver node som behandles til den noden vi kom fra i den til da korteste veien dit. Men hvis vi kommer til noden via en ny vei som har samme lengde som sist, så gjør vi ingen endring. Vi kan endre det slik at også den noden blir registrert. Det får vi til ved å bruke en liste for forrige-noder. Klassen Node blir da slik (endringen er markert med rødt):

  private static final class Node              // en indre klasse
  {
    private static final int uendelig = 0x7fffffff;  // maks int-verdi

    private final String navn;                 // navn/identifikator
    private final List<Kant> kanter;           // nodens kanter

    private int avstand = uendelig;            // til senere bruk
    private boolean ferdig = false;            // til senere bruk
    private List<Node> forrige;                // en liste

    private Node(String navn)                  // konstruktør
    {
      this.navn = navn;                        // nodens navn
      kanter = new LinkedList<>();             // kantliste
    }

    @Override
    public String toString() { return navn; }  // toString

  } // Node

I metoden kortestVeiFra() (vi bruker den forbedrede versjonen fra Programkode 11.2.3 d) må forrige-listen opprettes første gang vi kommer til en node. Hvis vi kommer til noden via en ny vei med samme lengde, legger vi til forrige på den veien, og hvis vi kommer dit via en kortere vei, tømmer vi listen før vi legger inn.

  public void kortestVeiFra(String nodenavn)  // Dijkstras metode
  {
    Node start = noder.get(nodenavn); // henter startnoden
    if (start == null) throw new NoSuchElementException(nodenavn + " er ukjent!");

    class Avstand  // lokal hjelpeklasse
    {
      Node node;
      int avstand;

      Avstand(Node node, int avstand)  // konstruktør
      {
        this.node = node; this.avstand = avstand;
      }
    }

    PriorityQueue<Avstand> aktiv = new PriorityQueue<>((a,b) -> a.avstand - b.avstand);

    start.avstand = 0;                       // avstand settes til 0
    aktiv.offer(new Avstand(start, 0));      // startnoden er nå aktiv

    while (!aktiv.isEmpty())                 // så lenge det er aktive noder
    {
      Avstand denne = aktiv.poll();          // den med minst avstandsverdi

      for (Kant k : denne.node.kanter)       // de direkte etterfølgerne
      {
        Node etterfølger = k.til;            // k er en kant fra denne 

        if (etterfølger.ferdig) continue;    // ser ikke på de som er ferdige

        int nyavstand = denne.avstand + k.vekt;

        if (nyavstand < etterfølger.avstand)
        {
          etterfølger.avstand = nyavstand;  // oppdaterer
          aktiv.offer(new Avstand(etterfølger, etterfølger.avstand));

          if (etterfølger.forrige == null)             // noden er ubehandlet
            etterfølger.forrige = new LinkedList<>();  // oppretter listen
          else
            etterfølger.forrige.clear();               // tømmer listen

          etterfølger.forrige.add(denne.node);         // legger inn
        }
        else if (nyavstand == etterfølger.avstand)      // ny vei - samme avstand
        {
          etterfølger.forrige.add(denne.node);
        }
      } // for

      denne.node.ferdig = true;            // denne er ferdig

    } // while
  }

Metoden veiTil() må endres. Vi kan lage den slik at den returnerer én av de korteste veiene hvis det er flere. Når vi går «bakover» fra tilnoden, kan vi f.eks. konsekvent gå til den første i forrige-listen:

  public String veiTil(String nodenavn)
  {
    Node node = noder.get(nodenavn);
    if (node == null) throw new NoSuchElementException(node + " er ukjent!");

    Deque<String> kø = new LinkedList<>();
    if (node.forrige == null) return kø.toString();  // ingen vei hit

    kø.add(nodenavn);
    while (node.forrige != null)   // startnoden har ingen forrige-liste
    {
      node = node.forrige.get(0);  // den første i forrige-listen
      kø.addFirst(node.navn);
    }

    return kø.toString();
  }

Med disse endringene vil flg. kode virke:

  String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap11/2/vgraf63.txt";
  VGraf vgraf = new VGraf(url);

  String fra ="0", til = "62";
  vgraf.kortestVeiFra(fra);

  System.out.println(vgraf.veiTil(til) + ", " + vgraf.avstand(til));

  // Utskrift: [0, 3, 8, 15, 24, 33, 42, 50, 57, 61, 62], 18

Men målet var å finne alle korteste veier hvis det er flere. I VGraf63 er det som tidligere nevnt, fem forskjellige korteste veier (lengde 18) fra 0 og 62. De finner vi f.eks. ved å gjøre en rekursiv travsering av grafen. Da starter vi i tilnoden og går bakover ved hjelp av forrige-listene. Hver gang vi da kommer til franoden, skriver vi ut hvilken vei vi har gått. Vi holder orden på veien ved å bruke en stakk. Stakken inneholder nodene i rett rekkefølge:

  public List<String> kortesteVeier(String nodenavn)
  {
    List<String> liste = new ArrayList<>();
    Deque<String> stakk = new ArrayDeque<>();

    Node node = noder.get(nodenavn);
    if (node == null) throw new NoSuchElementException(node + " er ukjent!");

    if (node.forrige == null) return liste;  // ingen vei til denne noden

    veier(node, liste, stakk);               // kaller rekursiv metode

    return liste;                            // liste med veier
  }

  private void veier(Node p, List<String> liste, Deque<String> stakk)
  {
    if (p.forrige == null)  // vi har kommet til franoden
    {
      stakk.push(p.navn);   // legger på stakken

      liste.add(stakk.toString());  // legger inn veien i listen

      stakk.pop();     // fjerner fra stakken
    }
    else
    {
      stakk.push(p.navn);  // legger på stakken

      for (int i = 0; i < p.forrige.size(); i++)  // grenene
      {
        veier(p.forrige.get(i), liste, stakk);
      }

      stakk.pop();   // fjerner fra stakken
    }
  }

Med disse metodene vil flg. kode virke:

  String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap11/2/vgraf63.txt";
  VGraf vgraf = new VGraf(url);

  String fra ="0", til = "62";
  vgraf.kortestVeiFra(fra);

  List<String> liste = vgraf.kortesteVeier(til);
  for (String vei : liste) System.out.println(vei);

  // Utskrift: 
  // [0, 3, 8, 15, 24, 33, 42, 50, 57, 61, 62]
  // [0, 2, 7, 14, 22, 32, 41, 49, 56, 60, 62]
  // [0, 3, 8, 15, 24, 33, 42, 41, 49, 56, 60, 62]
  // [0, 1, 4, 11, 19, 28, 38, 47, 55, 60, 62]
  // [0, 2, 7, 14, 22, 31, 40, 48, 55, 60, 62]

Oppgave 7

Forslag kommer senere.

Oppgave 8

VGraf skal ha en privat variabel start av type Node. Dvs. slik

  private final Map<String, Node> noder;       // en map til å lagre nodene
  private Node start;                          // startnode for korteste vei

  public VGraf()                               // standardkonstruktør
  {
    noder = new TreeMap<>();                   // oppretter en TreeMap
    start = null;
  }

Variabelen start bør «nulles» i metoden nullstill():

  public void nullstill()
  {
    for (Node node : noder.values())
    {
      node.avstand = Node.uendelig;
      node.ferdig = false;
      node.forrige = null;
    }
    start = null;
  }

Vi gjør endringene i versjonen av korteste vei fra Oppgave 3 (Obs: Hvis du ikke har Java 10 eller senere, må du ta vekk bruken av var og isteden bruke vanlig typedeklarasjon):

  public void kortestVeiFra(String nodenavn)  // Dijkstras metode
  {
    start = noder.get(nodenavn); // henter startnoden
    if (start == null) throw new NoSuchElementException(nodenavn + " er ukjent!");

    class Avstand
    {
      Node node;
      int avstand;

      Avstand(Node node, int avstand)
      {
        this.node = node; this.avstand = avstand;
      }
    }

    var aktiv = new PriorityQueue<Avstand>((a,b) -> a.avstand - b.avstand);

    for (Kant k : start.kanter)  // de direke etterfølgeren til startnoden
    {
      k.til.avstand = k.vekt;
      aktiv.offer(new Avstand(k.til, k.vekt));  // etterfølgeren blir aktiv
    }

    while (!aktiv.isEmpty())                 // så lenge det er aktive noder
    {
      var denne = aktiv.poll();              // tar ut den "minste" noden
      denne.node.ferdig = true;              // den er ferdig

      for (Kant k : denne.node.kanter)       // de direkte etterfølgerne
      {
        var etterfølger = k.til;             // k er en kant fra denne 

        if (etterfølger.ferdig) continue;    // ser ikke på de som er ferdige

        if (denne.avstand + k.vekt < etterfølger.avstand)
        {
          etterfølger.avstand = denne.avstand + k.vekt;
          aktiv.offer(new Avstand(etterfølger, etterfølger.avstand));
          etterfølger.forrige = denne.node;
        }
      } // for
    } // while
  }

Metoden veiFra() må få et tillegg:

  public String veiTil(String nodenavn)
  {
    Node node = noder.get(nodenavn);
    if (node == null) throw new NoSuchElementException(node + " er ukjent!");

    Deque<String> kø = new LinkedList<>();
    while (node != null)
    {
      kø.addFirst(node.navn);
      node = node.forrige;
    }

    kø.addFirst(start.navn);
    return kø.toString();
  }

Bruker vi denne nye versjonen av kortestVeiFra() vil flg. kode gi utskriften nedenfor:

  String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap11/2/vgraf3.txt";
  VGraf vgraf = new VGraf(url);

  String nodenavn = "A";
  vgraf.kortestVeiFra(nodenavn);

  for (String n: vgraf)
  {
    System.out.println(
      "Korteste vei fra " + nodenavn + " til " +
      n + ": " + vgraf.veiTil(n) + " lengde: " + vgraf.avstand(n));
  }

  Korteste vei fra A til A: [A, F, D, A] lengde: 6
  Korteste vei fra A til B: [A, B] lengde: 4
  Korteste vei fra A til C: [A, B, C] lengde: 8
  Korteste vei fra A til D: [A, F, D] lengde: 4
  Korteste vei fra A til E: [A, B, E] lengde: 7
  Korteste vei fra A til F: [A, F] lengde: 3
  Korteste vei fra A til G: [A, F, D, G] lengde: 7
  Korteste vei fra A til H: [A, B, E, H] lengde: 9
  Korteste vei fra A til I: [A, F, I] lengde: 4
  Korteste vei fra A til J: [A, F, I, L, J] lengde: 8
  Korteste vei fra A til K: [A, K] lengde: 2147483647
  Korteste vei fra A til L: [A, F, I, L] lengde: 7
  Korteste vei fra A til M: [A, F, I, N, Q, O, M] lengde: 11
  Korteste vei fra A til N: [A, F, I, N] lengde: 6
  Korteste vei fra A til O: [A, F, I, N, Q, O] lengde: 10
  Korteste vei fra A til P: [A, P] lengde: 2147483647
  Korteste vei fra A til Q: [A, F, I, N, Q] lengde: 9
  Korteste vei fra A til R: [A, F, I, N, Q, O, M, R] lengde: 14