mirror of
https://github.com/TheAlgorithms/C.git
synced 2026-02-12 21:39:06 +00:00
Shortest path #39
Reference in New Issue
Block a user
Delete Branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Originally created by @Shreya2704 on GitHub (Oct 28, 2019).
To find the shortest path between 2 cities
@ghost commented on GitHub (Feb 2, 2020):
Hi can i take up this issue ?
Plus any specific algortihm you have in mind ?
@ghost commented on GitHub (Feb 3, 2020):
hi @Shreya2704 can you verify if the issue is resolved ? I have done a pull request for this ...if you find this solves your problem kindly merge it or if further additions need to be made ,please list them here.
@deadshotsb commented on GitHub (May 18, 2020):
@sagnik-chatterjee Well the Djikstra's algorithm can be used to find a single source shortest path, but as "To find the shortest path between 2 cities", I find it more like applying an all pair Shortest path (floyd warshall algorithm) You may consider adding a dynamic programming approach for that, you may refer to: https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
@Manavpreeet commented on GitHub (May 20, 2020):
Can i take this issue ? Let me know if you have any particular choice !
@plongueira commented on GitHub (May 21, 2020):
Maybe use discrete mathematics theory for example directed graphs and weighted graphs could solve the problem (i.e) the distance between 2 cities without a direct connection is unknown so in order to get a close reflect of the reality you could check different paths between those two cities,then adding the weights between each pair of cities from city source to destiny and that'd be all
@deadshotsb commented on GitHub (May 24, 2020):
@ManavpreetSingh Yes sure
@ashwinshaji6679 commented on GitHub (Aug 27, 2021):
Can I take up this issue
@Panquesito7 commented on GitHub (Aug 27, 2021):
Thank you for your interest in contributing. 👍
Before submitting a PR, please ensure the following:
I'll look forward to reviewing your pull request as soon as I can. Thanks. 🙂
@HybridDog commented on GitHub (Oct 4, 2021):
In practice, e.g. in a car navigation system, the graph is preprocessed so that the distance between two cities can later be queried in e.g. O(sqrt(n) log(n)), which is a lot faster than Dijkstra's algorithm (excluding the preprocessing time).
https://en.wikipedia.org/wiki/Contraction_hierarchies
@github-actions[bot] commented on GitHub (Dec 11, 2021):
This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
@github-actions[bot] commented on GitHub (Dec 18, 2021):
Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!