Time complexity of Johnson's algorithm wrongly stated in documentation
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 2/5
- Tempo stimato
- 1-3 ore
- Idoneità per principianti
- 38/100
- Tipo di issue
- Documentazione
- Chiarezza
- Abbastanza chiara
- Stato di attività
- Ferma
- Stack tecnologico
- julia
- Ambito
- documentation
Direzione di ricerca
Individua la documentazione di Johnson's all-pairs shortest path algorithm e leggi l'affermazione sulla complessità a cui si fa riferimento insieme al trattamento dei grafi pesati e non pesati da parte dell'algoritmo. Verifica i limiti appropriati per l'implementazione, quindi aggiorna la documentazione per distinguere tra i casi pesato e non pesato e confermare che la complessità indicata sia corretta.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
Description of bug
Describe the bug clearly and concisely.
The documentation to Johnson's all-pairs shortest path algorithm is stated as O(|V||E|). This cannot be true, in particular if Dijkstra's algorithm is finally called for weighted graphs. If Dijkstra's algorithm uses a Fibonacci heap (I didn't look if this is the case here), the runtime is O(|V|^2 log |V|+|V|⋅|E|), which is a big difference for sparse graphs.
Only in case of an unweighted graph, one can achieve time O(|V||E|) by calling breadth first search from each node.
- Lingua principale
- Julia
- Stelle
- 540
- Fork
- 130
- Metriche di merge delle PR
- Nessuna PR unita negli ultimi 30g
Preparare l'ambiente
- Nessun Dockerfile né file Docker Compose
- Ha un modello di pull request
- Leggi la guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di JuliaGraphs/Graphs.jl
-
Difficoltà 5/5 Più di una settimana Idoneità per principianti 35/100
JuliaGraphs/Graphs.jl#521 ·
-
Difficoltà 5/5 Più di una settimana Idoneità per principianti 42/100
JuliaGraphs/Graphs.jl#504 · 4 commenti ·
-
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 55/100
JuliaGraphs/Graphs.jl#498 · 1 commento ·
-
Difficoltà 3/5 1-2 giorni Idoneità per principianti 42/100
JuliaGraphs/Graphs.jl#497 · 1 commento ·
-
good first issue
Difficoltà 3/5 1-2 giorni Idoneità per principianti 35/100
JuliaGraphs/Graphs.jl#483 · 3 commenti ·
Tutte le issue di JuliaGraphs/Graphs.jl
Issue simili
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 76/100
legend-exp/LegendDataManagement.jl#232 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 76/100
EnzymeAD/Reactant.jl#3569 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 67/100
astroautomata/SymbolicRegression.jl#783 ·
I maintainer di solito rispondono entro 1 giorno
-
bug
Difficoltà 2/5 1-3 ore Idoneità per principianti 73/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 90/100
I maintainer di solito rispondono entro 1 giorno