Dijkstran algoritmi ei anna välttämättä oikeaa vastausta, jos verkossa on negatiivisen painoisia kaaria.
Tehtäväsi on rakentaa verkko, jossa kurssimateriaalin Dijkstran algoritmin toteutus antaa väärän vastauksen. Verkolla tulee olla seuraavat ominaisuudet:
- Verkossa on n solmua, jotka on numeroitu 1,2,\dots,n.
- Saat päättää itse verkon kaarten määrän.
- Jokainen kaari on suunnattu ja kaaren paino on kokonaisluku.
- Verkossa ei ole kahta kaarta samasta lähtösolmusta samaan kohdesolmuun.
- Verkossa ei ole kaarta, jonka lähtösolmu ja kohdesolmu ovat samat.
- Lyhimmän polun pituus solmusta 1 solmuun n on a, mutta Dijkstran algoritmi antaa vastauksen b.
Toteuta tiedostoon pathfail.py funktio create_edges, joka muodostaa halutunlaisen verkon. Funktion tulee palauttaa listana verkon kaaret.
Esimerkiksi lista [(1, 2, 5), (1, 3, 1)] tarkoittaisi, että verkossa on kaksi kaarta. Ensimmäinen kaari kulkee solmusta 1 solmuun 2 ja sen paino on 5. Toinen kaari kulkee solmusta 1 solmuun 3 ja sen paino on 1.
Voit muodostaa minkä tahansa verkon, jolla on halutut ominaisuudet. Voit olettaa, että funktiota testataan vain parametreilla, joilla verkko voidaan muodostaa.
class BellmanFord:
# voit kopioida tämän luokan kurssimateriaalista
class Dijkstra:
# voit kopioida tämän luokan kurssimateriaalista
def create_edges(n, a, b):
# TODO
def find_answer(my_class, n, edges):
nodes = range(1, n + 1)
finder = my_class(nodes)
for edge in edges:
finder.add_edge(edge[0], edge[1], edge[2])
distances = finder.find_distances(1)
return distances[n]
if __name__ == "__main__":
n = 100
edges = create_edges(n, 42, 1337)
answer1 = find_answer(BellmanFord, n, edges)
print(answer1) # 42
answer2 = find_answer(Dijkstra, n, edges)
print(answer2) # 1337