Suunnattu painotettu verkko on aluksi tyhjä. Tehtäväsi on toteuttaa luokka, jonka avulla voi lisätä kaaria verkkoon sekä tarkastaa, onko verkossa äärettömän lyhyttä polkua tietystä solmusta toiseen.
Toisin sanoen tehtävänä on selvittää, onko verkossa kahta solmua ja niin, että jos on olemassa mikä tahansa polku solmusta solmuun , voidaan löytää aina toinen polku, joka on vielä lyhempi.
Voit olettaa, että solmuja on enintään , luokan metodeita kutsutaan enintään kertaa ja jokaisen kaaren paino on välillä .
Toteuta tiedostoon shortening.py
luokka Shortening
, jossa on seuraavat metodit:
- konstruktori, jolle annetaan solmujen määrä
add_edge
lisää solmusta solmuun kaaren, jonka paino oncheck
palauttaaTrue
, jos solmusta solmuun on äärettömän lyhyt polku, ja muutenFalse
class Shortening: def __init__(self,n): # TODO def add_edge(self,a,b,x): # TODO def check(self,a,b): # TODO if __name__ == "__main__": s = Shortening(5) print(s.check(1,3)) # False s.add_edge(1,2,5) s.add_edge(2,3,-2) print(s.check(1,3)) # False s.add_edge(2,4,1) s.add_edge(4,2,-2) print(s.check(1,3)) # True