Title: feat: add A* search algorithm by InukaWijerathna · Pull Request #1909 · TheAlgorithms/JavaScript · GitHub
Open Graph Title: feat: add A* search algorithm by InukaWijerathna · Pull Request #1909 · TheAlgorithms/JavaScript
X Title: feat: add A* search algorithm by InukaWijerathna · Pull Request #1909 · TheAlgorithms/JavaScript
Description: The Graphs folder already has several shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) but no heuristic-guided search. This adds the A* search algorithm, which generally explores fewer nodes than Dijkstra's by using a heuristic to steer toward the target. Implementation notes: Reuses the existing KeyPriorityQueue (Data-Structures/Heap/KeyPriorityQueue.js) for the open set instead of introducing a new heap. Takes a general weighted adjacency-list graph ({ node: [[neighbor, weight], ...] }) and a heuristic(node) function, consistent with how other graph algorithms here take adjacency-list/edge-list input. Passing a heuristic that always returns 0 makes it behave exactly like Dijkstra's algorithm, which is covered by a test. Returns { path, cost } for the shortest path, or null if the target is unreachable. Test plan Graphs/test/AStar.test.js covers: a weighted graph with an admissible heuristic, the zero-heuristic/Dijkstra-equivalent case, start === target, and an unreachable target. Ran the full suite locally (npm test): 347 test files, 11,975 tests passing. npm run check-style passes.
Open Graph Description: The Graphs folder already has several shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) but no heuristic-guided search. This adds the A* search algorithm, which generally explores f...
X Description: The Graphs folder already has several shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) but no heuristic-guided search. This adds the A* search algorithm, which generally explores f...
Opengraph URL: https://github.com/TheAlgorithms/JavaScript/pull/1909
X: @github
Domain: Github.com
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:eae4fa1c-78de-c14a-c205-712f7b4ec83e |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | B04E:9BC0B:9EDBF4:E1F128:6A63162F |
| html-safe-nonce | 795172c232a743cd8f0f3e317f62cf95a29b49538656723e81e8fa31d882475e |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJCMDRFOjlCQzBCOjlFREJGNDpFMUYxMjg6NkE2MzE2MkYiLCJ2aXNpdG9yX2lkIjoiNTAwMzE2MjEwNTg3NTIwNzcyNyIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | ba2404810a97095110bf825e22da122baa62ae85bf30733ed226ce292c6a162b |
| hovercard-subject-tag | pull_request:3946420502 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/TheAlgorithms/JavaScript/pull/1909/files |
| twitter:image | https://avatars.githubusercontent.com/u/180553425?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/180553425?s=400&v=4 |
| og:image:alt | The Graphs folder already has several shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) but no heuristic-guided search. This adds the A* search algorithm, which generally explores f... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 1a6c056e02f174fffc096c521ec0ff6fb83e40a2ec8cb8875466ec1524872dd6 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/TheAlgorithms/JavaScript git https://github.com/TheAlgorithms/JavaScript.git |
| octolytics-dimension-user_id | 20487725 |
| octolytics-dimension-user_login | TheAlgorithms |
| octolytics-dimension-repository_id | 97086543 |
| octolytics-dimension-repository_nwo | TheAlgorithms/JavaScript |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 97086543 |
| octolytics-dimension-repository_network_root_nwo | TheAlgorithms/JavaScript |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 6a93e25585f487ddff9e3996c06d5b869d6e1828 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width