bellmanFord: runs in O(V²·E) rather than the O(V·E) / O(E) stated in README
Avaliação
- Dificuldade
- 2/5
- Tempo estimado
- 1-3 horas
- Facilidade para iniciantes
- 35/100
- Tipo de issue
- Bug
- Clareza
- Claramente especificada
- Status de atividade
- Estagnada
- Stack de tecnologia
- javascript
Direção de pesquisa
Start with bellmanFord.js lines 21–39 and inspect how it finds edges and handles each relaxation pass. The issue proposes iterating vertex.getEdges() and stopping when a pass makes no changes; check the linked pull request #2245 for work already underway. Done means the algorithm avoids repeated edge searches and exits early when a pass makes no changes, while preserving correct results.
Escrita pelo modelo de indexação a partir do texto da issue.
Descrição
bellmanFord.js (lines 21–39) finds each edge again via graph.findEdge, which is a linear scan of the vertex's edge list, and has no early exit when a pass relaxes nothing. On complete digraphs with unit weights (a best-case input):
| V | node visits | visits / (V·E) | time |
|---|---|---|---|
| 20 | 79,420 | 10.4 | 3 ms |
| 40 | 1.28M | 20.5 | 10 ms |
| 80 | 20.5M | 40.5 | 136 ms |
| 160 | 327.6M | 80.5 | 1.8 s |
Fix: iterate vertex.getEdges() directly (this also fixes #2230) and stop when an iteration changes nothing.
Found during an independent property-based audit of this repo (full report and reproducible harness: https://github.com/devladpopov/algorithm-autopsy/tree/main/autopsy-02).
- Linguagem predominante
- JavaScript
- Estrelas
- 197k
- Forks
- 31k
- Métricas de merge de PRs
- Nenhum PR com merge em 30d
Preparar o ambiente
- Sem Dockerfile nem arquivo Docker Compose
- Sem modelo de pull request
- Ler o guia de contribuição
Primeiros passos
- Leia a issue inteira e depois o guia de contribuição do projeto.
- Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
- Faça um fork do repositório e trabalhe em uma branch.
- Abra um pull request que referencie o número da issue.
Mais de trekhleb/javascript-algorithms
-
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 78/100
trekhleb/javascript-algorithms#2231 · 1 comentário ·
-
[Docs]: 9 hotlinked images in algorithm READMEs return 404 (GeeksforGeeks + ivanyu.me uploads)Aberta
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 76/100
trekhleb/javascript-algorithms#2225 ·
-
BinarySearchTreeNode removingTalvez já em andamento @bbonch assumiu há 264 dias. Aberta
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 72/100
trekhleb/javascript-algorithms#2102 · 1 comentário ·
-
math: uniquePaths and leastCommonMultiple return non-integers below 2^53; iterative Euclid is subtraction-based and can hangTalvez já em andamento @Shubham-Padkonde assumiu há 7 dias. Aberta
Dificuldade 3/5 1-2 dias Facilidade para iniciantes 35/100
trekhleb/javascript-algorithms#2238 ·
-
Trie.deleteWord fails for words containing characters outside the BMP (e.g. emoji)Talvez já em andamento @Shubham-Padkonde assumiu há 7 dias. Aberta
Dificuldade 1/5 Menos de uma hora Facilidade para iniciantes 35/100
trekhleb/javascript-algorithms#2237 ·
Todas as issues de trekhleb/javascript-algorithms
Issues semelhantes
-
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 70/100
solana-foundation/solana-web3.js#4015 · 1 comentário ·
Mantenedores costumam responder em até 1 dia
-
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 82/100
gramps-project/gramps-web#1604 ·
Mantenedores costumam responder em até 1 dia
-
enhancement good first issue hacktoberfest help wanted
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 85/100
BinaryBaconLabs/todo-app#18 ·
-
Cache airport lookupsAbertaenhancement
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 66/100
sutantyo/flight-watch#32 ·
Mantenedores costumam responder em até 1 dia
-
bug
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 88/100
Mantenedores costumam responder em até 1 dia