Content-Length: 256840 | pFad | http://github.com/TheAlgorithms/Go/pull/781

99 fix: improve Dijkstra algorithm with proper min-heap implementation by Verryx-02 · Pull Request #781 · TheAlgorithms/Go · GitHub
Skip to content

fix: improve Dijkstra algorithm with proper min-heap implementation #781

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 1 commit into
base: master
Choose a base branch
from

Conversation

Verryx-02
Copy link

@Verryx-02 Verryx-02 commented Jul 1, 2025

Description of Change

This PR significantly improves the Dijkstra algorithm implementation in graph/dijkstra.go by addressing several critical issues found in the current implementation:

Problems Fixed:

  • MaxHeap/MinHeap confusion with misleading comments
  • Type safety issues with interface{} usage and unsafe casts
  • Missing error handling and input validation
  • Incomplete documentation and test coverage

Improvements Made:

  • Proper min-heap implementation using container/heap
  • Complete type safety with dedicated structs
  • Robust error handling with comprehensive input validation
  • Early termination optimization for better performance
  • Full GoDoc documentation following project standards
  • 100% backward compatibility maintained

New Features Added:

  • DijkstraWithPath() - Returns complete shortest path reconstruction
  • DijkstraAllPairs() - Computes distances to all reachable nodes
  • Comprehensive test suite with edge cases, benchmarks, and stress tests

Performance & Quality:

  • Maintains O((V+E) log V) time complexity
  • Improved memory management and overflow protection
  • Extensive test coverage including error conditions
  • Full backward compatibility - existing code continues to work unchanged

Checklist

  • Added description of change
  • Added file name matches File name guidelines
  • Added tests and example, test must pass
  • Added documentation so that the program is self-explanatory and educational - GoDoc guidelines
  • Relevant documentation/comments is changed or added
  • PR title follows semantic commit guidelines
  • Search previous suggestions before making a new one, as yours may be a duplicate
  • I acknowledge that all my contributions will be made under the project's license

Notes: This improvement maintains 100% backward compatibility while fixing critical algorithmic and type safety issues. All existing code using Dijkstra() will continue to work unchanged, but with better performance and reliability.

- Replace MaxHeap confusion with dedicated min-heap using container/heap
- Add comprehensive input validation and error handling
- Improve type safety by removing interface{} usage
- Add early termination optimization for better performance
- Maintain backward compatibility with existing API
- Add DijkstraWithPath() and DijkstraAllPairs() functionality
- Include comprehensive test suite with edge cases and benchmarks

fix: typo in .github/ISSUE_TEMPLATE/bug_report.yml
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

1 participant








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: http://github.com/TheAlgorithms/Go/pull/781

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy