Laboration 1, Grafer

Laborationen behandlar elementära grafalgoritmer.

Syfte

Implementera elementära grafalgoritmer. Sökning med DFS och BFS. Dijkstras algoritm.

Tidsåtgång

Ett tillfälle är avsatt för detta moment.

Uppgifter

Läs in indatat, en adjacency matris.

Implementera Depth-First Search och Breath-First Search för att avgöra om grafen är sammanhängande **

Om du finner bekymmer i grafen ange hur du rättar till dessa.

Implementera Dijkstras algoritm.

- Hur lång är vägen mellan Nackstavägen till Förrådet? Beskriv promenaden.

- Hur lång är vägen mellan L319 och D025?

- Hur lång är vägen från Universitetet till Bite Line Västra?

Se även tips.

Verktyget som använts för att skapa export.txt kan du hämta.

** -(Clarification: DFS and BFS have to be used to check that the graph is valid. A disconnected graph would be an example of an invalid graph. So, your need to use BFS and DFS to make sure that EVERY node in the graph can be reached from ANY node in the graph. /Elijs)