Shortest path

[Shreya2704]

To find the shortest path between 2 cities

Hi can i take up this issue ?
Plus any specific algortihm you have in mind ?

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]

@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]

Can i take this issue ? Let me know if you have any particular choice !

[plongueira]

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]

@manavpreetsingh Yes sure

[ashwinshaji6679]

Can I take up this issue

[Panquesito7]

Can I take up this issue

Thank you for your interest in contributing. 👍
Before submitting a PR, please ensure the following:

• The algorithm isn't a duplicate in this repository.
• Make your code as per the repository standards.
• Ensure that all the automated-tests pass.

I'll look forward to reviewing your pull request as soon as I can. Thanks. 🙂

[HybridDog]

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]

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]

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!