Grafy

Zadanie z8.1. Zadanie tablicowe

Zadanie 8.2. (5 punktów) W pliku graf.pdf znajduję się przykład mapy, na której są miejsca oznaczone kolejnymi liczbami 0,1, ... oraz drogi łączące te miejsca. Drogi mają przypisane długości i średnie prędkości przejazdu. Taką mapę będziemy reprezentować jako graf nieskierowany z wagami na krawędziach.

Napisz i przetestuj program, który umożliwia wykonanie następujących operacji

1. Przeczytanie z pliku tekstowego danych pozwalających zbudować graf reprezentujący mapę. W pierwszym wierszu pliku jest ilość miejsc, a w kolejnych wierszach są czwórki odpowiadające drogom między miejscami: czwórka (u,v,d,s) oznaczają drogę z miejsca u do miejsca v o długości d o średniej prędkości przejazdu s. Graf powinien być reprezentowany w programie jako lista sąsiedztw. (1 punkt)
2. dla danych miejsc u i v wyliczyć i wypisać trasę przejazdu o najmniejszej długości (1 punkt)
3. dla danych miejsc u i v wyliczyć i wypisać trasę przejazdu o najmniejszym czasie przejazdu (d/s) (1 punkt)
4. znaleźć optymalne miejsce, w którym miejscu powinien stać pojazd straży pożarnej. Optymalne miejsce to takie, żeby maksimum z czasów przejazdu do wszystkich innych miejsc było najmniejsze (1 punkt)
5. dołączyć do grafu nową krawędź odpowiadającą nowej drodze (0.5 punkta)
6. usunąć z grafu krawędź odpowiadającą jakiejś drodze (0.5 punkta)

Uwagi.

• Zakładamy, że zawsze mamy do czynienia z grafem spójnym, chociaż tego nie sprawdzamy w programie. Czyli użytkownik jest odpowiedzialny za podawanie dobrych danych.
• Załączony plik z grafem jest tylko przykładem. Można program tworzyć na bazie mniejszego, własnego grafu.
• Testowanie może być zrobione w programie "na sztywno", niekoniecznie przez jakieś menu wyboru.