PricingLoginStart free
DSA Interview Prep · Oppitunti

Floyd–Warshall: kaikkien solmuparien lyhimmät polut

Täyttäkää kaikkien solmuparien etäisyysmatriisi kolmen sisäkkäisen silmukan Floyd–Warshall-algoritmilla ja käyttäkää sitä kaikkien solmuparien pienimmän hyppymäärän etsimiseen.

Oppitunti 3/413 vaihetta

Floyd–Warshall: kaikkien solmuparien lyhimmät polut on ilmainen DSA Interview Prep-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu DSA Interview Prep-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.

Kaikkien solmuparien lyhimmät polut

Floyd-Warshall laskee lyhimmät polut jokaisen solmuparin välillä painotetussa graafissa — myös graafeissa, joissa on negatiivisia kaaripainoja, mutta ei negatiivisia syklejä. Dijkstran suorittaminen jokaisesta lähteestä maksaa O(V × (V+E) log V), kun taas Floyd-Warshallin aikavaativuus on O(V³) kaaritiheydestä riippumatta. Tiheissä graafeissa, joissa V ≤ 500, Floyd-Warshall on usein yksinkertaisempi ja suunnilleen yhtä nopea.

Ydinajatus: välisolmut

Floyd-Warshallin keskeinen havainto on seuraava: dp[i][j][k] = lyhin polku solmusta i solmuun j, kun välisolmuina saa käyttää vain solmuja {0, 1, ..., k}. Lyhin polku joko käyttää solmua k välisolmuna tai ei käytä sitä. Jos käyttää: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Jos ei käytä: dp[i][j][k] = dp[i][j][k-1]. Koska kolmas ulottuvuus etenee vain eteenpäin, se voidaan poistaa — päivitykset tehdään paikallaan.

Etäisyysmatriisin alustus

Aloittakaa V×V-matriisilla: dist[i][i] = 0 (etäisyys solmusta itseensä on nolla), dist[i][j] = weight suorille kaarille ja dist[i][j] = inf kaarittomille solmuparien yhteyksille. Käykää sitten läpi kaikki välisolmut k ja päivittäkää solmuparit (i, j). Silmukan k ympärillä on oltava ulommaisena, jotta polut muodostuvat oikein kasvavan sallitun välisolmujoukon kautta.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

Täydellinen toteutus esimerkkeineen

Tarkastellaan Floyd-Warshallia neljän solmun graafissa. Kun jokainen välisolmu k on käsitelty, matriisiin muodostuu lyhyempiä polkuja, jotka kulkevat solmun k kautta. Algoritmi käsittelee luonnostaan usean siirtymän polut rakentamalla lyhyimmät polut vaiheittain.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

Negatiivisten syklien tunnistaminen

Floyd-Warshallin suorittamisen jälkeen tarkistakaa päädiagonaali: jos jokin dist[i][i] < 0, solmun i kautta kulkee negatiivinen sykli. Tämä johtuu siitä, että negatiivinen sykli mahdollistaa paluun solmuun i solmusta i negatiivisella kustannuksella. Jos negatiivisia syklejä ei ole, kaikki diagonaalin arvot pysyvät nollina.

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

Polun rekonstruointi

Voitte rekonstruoida varsinaisen polun solmusta i solmuun j ylläpitämällä next[i][j]-matriisia: alustakaa suorille kaarille next[i][j] = j. Kun päivitys tehdään välisolmun k kautta, asettakaa next[i][j] = next[i][k]. Polun palauttamiseksi aloittakaa solmusta i ja seuratkaa next-osoittimia, kunnes saavutatte solmun j. Tämä lisää tilavaativuuteen O(V²) ja tekee kunkin polun rekonstruoinnista O(V):n.

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

Transitiivinen sulkeuma

Yksinkertaisempi muunnelma, transitiivinen sulkeuma, vastaa kaikkien solmuparien osalta kysymykseen ”onko solmu j saavutettavissa solmusta i?”. Etäisyydet korvataan totuusarvoilla: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Tämä on Floyd-Warshall, jossa yhteenlaskun ja minimioperaation sijaan käytetään totuusarvojen OR-operaatiota. Alustakaa reach[i][i] = True ja asettakaa reach[i][j] = True suorille kaarille.

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

Aikavaativuus ja käyttötilanteet

Floyd-Warshall: O(V³) aikavaativuus, O(V²) tilavaativuus. Tiheissä graafeissa (E ≈ V²), joissa V ≤ 300, tämä on nopeampi kuin Dijkstran suorittaminen V kertaa (myös O(V³) tässä tapauksessa). Harvoissa graafeissa, joissa V = 1000 ja E = 3000, Dijkstran suorittaminen V kertaa maksaa O(V×E×log V) ≈ 33M, kun taas Floyd-Warshall maksaa O(V³) = 10⁹ — Dijkstra on parempi. Tietäkää, milloin kumpaakin algoritmia kannattaa käyttää.

Pienin hyppyjen määrä kaikkien solmuparien välillä

Asettakaa kaikkien kaarten painoksi 1 (tai käyttäkää totuusarvoista vierekkäisyysmatriisia Floyd-Warshallilla ja käyttäkää min-operaation sijaan yhteenlaskua): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Tämä laskee pienimmän hyppyjen määrän kaikkien solmuparien välillä — tulos vastaa kaikkien parien BFS:ää, mutta se lasketaan yhdellä O(V³)-aikaisella Floyd-Warshall-läpikäynnillä.

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

Haastattelukonteksti: milloin haastattelijat kysyvät Floyd-Warshallista

Floyd-Warshall tulee haastatteluissa vastaan tehtävissä, joissa: (1) etsitään kaikkien solmuparien etäisyyksiä pienestä graafista, (2) selvitetään, onko graafissa sykliä, jonka kokonaispaino on negatiivinen, (3) lasketaan lyhimpiä polkuja rajoitteiden välitys -ongelmissa tai (4) pyydetään nimenomaisesti O(V³)-aikaista ratkaisua, kun V ≤ 200. Mainitkaa aina kolmen silmukan rakenne sekä se, että oikeellisuus edellyttää negatiivisten syklien puuttumista.

Floyd-Warshall suuntaamattomissa graafeissa

Suuntaamattomissa graafeissa lisätkää jokaisesta kaaresta molemmat suunnat: dist[u][v] = dist[v][u] = weight. Muilta osin algoritmi on sama. Tuloksena oleva matriisi on symmetrinen: dist[i][j] == dist[j][i] kaikille solmuparille. Olkaa alustuksessa tarkkana, ettette vahingossa lisää suunnattuja kaaria — suuntaamattomat kaaret on lisättävä alkumatriisiin molempiin suuntiin ennen kolmen silmukan suorittamista.

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Pikatarkistus

Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteiden ymmärtämistä.

Vastaa interaktiivisessa oppitunnissa

Oppitunnin yhteenveto

Tässä oppitunnissa opitte, että Floyd-Warshall laskee kaikkien solmuparien lyhimmät polut kolmella sisäkkäisellä silmukalla ja rekurrenssilla dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), negatiiviset syklit voidaan havaita tarkistamalla, onko jokin dist[i][i] < 0 suorituksen jälkeen ja algoritmin aikavaativuus on O(V³) ja tilavaativuus O(V²). Seuraavaksi palaamme lyhimmän polun sovelluksiin Network Delay Timen ja polun rekonstruointitekniikoiden avulla.

Aloita maksutta

Opi Python tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit
30
Oppitunnit
120
Aloita opiskelu maksuttaNäytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Floyd–Warshall: kaikkien solmuparien lyhimmät polut” ilmainen?

Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa DSA Interview Prep-oppimispolun 3 oppituntia, myös oppitunnin “Floyd–Warshall: kaikkien solmuparien lyhimmät polut”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Floyd–Warshall: kaikkien solmuparien lyhimmät polut”?

Täyttäkää kaikkien solmuparien etäisyysmatriisi kolmen sisäkkäisen silmukan Floyd–Warshall-algoritmilla ja käyttäkää sitä kaikkien solmuparien pienimmän hyppymäärän etsimiseen. Harjoittelet DSA Interview Prep-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni DSA Interview Prep-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin DSA Interview Prep-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.

Kuinka kauan ”Floyd–Warshall: kaikkien solmuparien lyhimmät polut”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä DSA Interview Prep-oppitunnilla?

Kyllä. Jokainen DSA Interview Prep-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

  1. Dijkstran algoritmi prioriteettijonolla
  2. Bellman–Ford ja negatiiviset syklit
  3. Floyd–Warshall: kaikkien solmuparien lyhimmät polut
  4. Network Delay Time ja polun rekonstruointi
← Takaisin: DSA Interview Prep