Floyd-Warshall for alle par
Korteste stier mellem hvert par
Floyd-Warshall for alle par er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Alle par på én gang
Nogle gange har du brug for den korteste vej mellem alle par af knuder, ikke kun fra én kilde. Det er problemet med alle par.
Mød Floyd-Warshall
Floyd-Warshall udfylder en komplet afstandstabel for alle par med tre enkle indlejrede løkker og næsten ingen opsætning.
Afstandsmatricen
Brug en matrix, hvor dist[i][j] er den hidtil bedste omkostning fra i til j. Start med de direkte kanter, du får angivet.
dist = [[INF] * n for _ in range(n)]Sæt diagonalen
Alle knuder kan nå sig selv gratis, så sæt diagonalen dist[i][i] til nul, før du begynder at relaksere.
for i in range(n):
dist[i][i] = 0Idéen med en mellemliggende knude
Tricket er at tillade veje gennem en mellemliggende knude k og derefter undersøge, om en rute via k er billigere end at gå direkte.
Løkkernes rækkefølge betyder noget
Den ydre løkke er k, den valgte mellemknude. De indre løkker i og j prøver hvert par mod denne mellemknude.
for k in range(n):
for i in range(n):
for j in range(n):Relaksationstrinnet
For hvert par skal du relaksere gennem k: Hvis vejen fra i til k til j er kortere, opdaterer du dist[i][j] til den samlede omkostning.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]Hvorfor k ligger yderst
Når k er færdig, må alle par bruge mellemliggende knuder op til k. Ved at placere k yderst bevarer du denne garanti.
Negative kanter er i orden
Floyd-Warshall accepterer negative kanter, men ikke negative cykler. En negativ cykel efterlader en diagonalpost under nul.
Køretiden
Tre løkker over n knuder giver O(n^3)-tid og O(n^2)-plads, hvilket kun er praktisk, når n er nogle få hundrede.
Hvornår du skal vælge den
Vælg Floyd-Warshall, når grafen er lille og tæt, og du virkelig har brug for afstanden mellem alle par, ikke kun fra én kilde.
Hurtig kontrol
Hvilken løkke skal være den yderste i Floyd-Warshall?
Opsummering: Floyd-Warshall
Initialiser en matrix, sæt diagonalen til nul, og gennemløb derefter k, i, j, mens du relakserer gennem k. Korteste veje mellem alle par i O(n^3). 🧮
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Floyd-Warshall for alle par” gratis?
Ja — hele teksten til “Floyd-Warshall for alle par” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Floyd-Warshall for alle par”?
Korteste stier mellem hvert par Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Floyd-Warshall for alle par”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Dijkstra med en heap
- 0-1 BFS med en deque
- Bellman-Ford og negative kanter
- Floyd-Warshall for alle par