bellmanFord: runs in O(V²·E) rather than the O(V·E) / O(E) stated in README
Évaluation
- Difficulté
- 2/5
- Temps estimé
- 1-3 heures
- Accessibilité débutants
- 35/100
- Type d'issue
- Bug
- Clarté
- Clairement spécifiée
- Activité
- À l'abandon
- Stack technique
- javascript
Piste de recherche
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.
Rédigé par le modèle d'indexation à partir du texte de l'issue.
Description
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).
- Langage dominant
- JavaScript
- Étoiles
- 197k
- Forks
- 31k
- Métriques de merge des PR
- Aucune PR mergée en 30 j
Préparer son environnement
- Aucun Dockerfile ni fichier Docker Compose
- Aucun modèle de pull request
- Lire le guide de contribution
Par où commencer
- Lisez l'issue en entier, puis le guide de contribution du projet.
- Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
- Forkez le dépôt et travaillez sur une branche.
- Ouvrez une pull request qui référence le numéro de l'issue.
Autres issues de trekhleb/javascript-algorithms
-
Difficulté 2/5 1-3 heures Accessibilité débutants 78/100
trekhleb/javascript-algorithms#2231 ·
-
[Docs]: 9 hotlinked images in algorithm READMEs return 404 (GeeksforGeeks + ivanyu.me uploads)Ouverte
Difficulté 2/5 1-3 heures Accessibilité débutants 76/100
trekhleb/javascript-algorithms#2225 ·
-
BinarySearchTreeNode removingPeut-être pris @bbonch l’a pris il y a 260 jours. Ouverte
Difficulté 2/5 1-3 heures Accessibilité débutants 72/100
trekhleb/javascript-algorithms#2102 · 1 commentaire ·
-
math: uniquePaths and leastCommonMultiple return non-integers below 2^53; iterative Euclid is subtraction-based and can hangPeut-être pris @Shubham-Padkonde l’a pris il y a 2 jours. Ouverte
Difficulté 3/5 1-2 jours Accessibilité débutants 35/100
trekhleb/javascript-algorithms#2238 ·
-
Trie.deleteWord fails for words containing characters outside the BMP (e.g. emoji)Peut-être pris @Shubham-Padkonde l’a pris il y a 3 jours. Ouverte
Difficulté 1/5 Moins d'une heure Accessibilité débutants 35/100
trekhleb/javascript-algorithms#2237 ·
Toutes les issues de trekhleb/javascript-algorithms
Issues similaires
-
Difficulté 2/5 1-3 heures Accessibilité débutants 75/100
Les mainteneurs répondent en général sous 1 jour
-
Difficulté 1/5 Moins d'une heure Accessibilité débutants 72/100
Les mainteneurs répondent en général sous 1 jour
-
type/bug
Difficulté 2/5 1-3 heures Accessibilité débutants 62/100
flarum/framework#5301 · 1 commentaire ·
Les mainteneurs répondent en général sous 1 jour
-
Difficulté 2/5 1-3 heures Accessibilité débutants 82/100
AOSSIE-Org/BabyNest#284 ·
Les mainteneurs répondent en général sous 1 jour
-
status:untriaged
Difficulté 1/5 Moins d'une heure Accessibilité débutants 86/100
midnightntwrk/servicedesk#275 ·
Les mainteneurs répondent en général sous 1 jour