INDA - Uppgift 8 våren 2007 Uppgiften ska lämnas till din övningsledare på övningen den 27/3. För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.
java Path FROM TOFROM och TO är två heltal som anger en startnod och en slutnod i en graf. Programmet ska skriva ut noderna på någon väg från FROM till TO om det finns en sådan väg i grafen, annars skriver programmet ut en tom rad. Vägen ska innehålla minimalt antal noder. Använd breddenförstsökning. Grafen finns lagrad i en fil med namnet Distances.txt. Noderna är numrerade 0, 1, 2, ..., n-1. Filens första rad innehåller talet n. De andra raderna innehåller tre tal i, j och d separerade med blanktecken. Det positiva talet d anger avståndet mellan noderna i och j. Filen kan också innehålla "//"-kommentarer och tomma rader. Kommentarerna fungerar på samma sätt som i Java. Här är ett exempel på en fil som beskriver en liten graf. // This is a database with distances between a number // of cities. The cities are numbered 0, 1, 2, ..., n-1. // The first lines contains the integer n, i.e. the // number of cities. Each following line contains three // integers i, j, and d separated by spaces. The positive // number d is the distance between i and j. 6 // Size 0 1 100 // First edge 0 3 80 0 5 25 1 2 120 1 5 60 2 3 50 3 4 100 4 5 200 // Last edgeVid eventuella fel så ska programmet skriva ut ett relevant felmeddelande till stderr och inte skriva något på stdout.
Stefan Nilsson 2007-02-13 |