Väärä polku

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