Implement Dijkstra's Algorithm for Shortest Path

[staging-devin-ai-integration[bot]]

Implement Dijkstra's Algorithm for Shortest Path

This pull request adds an implementation of Dijkstra's algorithm to the algorithms repository. Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights.

Changes

1. Added graph/dijkstra.py:

   • Implements the dijkstra function that takes a graph represented as a dictionary and a start node.
   • Returns a dictionary with the shortest distances from the start node to all other nodes.
   • Includes type hints and docstrings for better readability and maintainability.
   • Provides an example usage in the __main__ section.

2. Added graph/test_dijkstra.py:

   • Implements unit tests for the dijkstra function.
   • Covers various scenarios including simple graphs, disconnected graphs, single-node graphs, and complex graphs.
   • Includes a test for error handling when the start node is not in the graph.

Implementation Details

The algorithm uses a priority queue (implemented with Python's heapq module) to efficiently select the next node to process. This ensures an optimal time complexity of O((V + E) log V), where V is the number of vertices and E is the number of edges in the graph.

Testing

The implementation has been thoroughly tested with various graph configurations to ensure correctness and robustness. All tests are passing.

Next Steps

• Consider adding more advanced graph algorithms (e.g., Bellman-Ford, Floyd-Warshall).
• Explore optimizations for large-scale graphs.

This implementation was created as part of a Devin run. You can find the details of the run here: https://staging.itsdev.in/devin/972023a91df94403a18c3e6f869b61a4

@Federico, could you please review this implementation and provide any feedback or suggestions for improvement? Thank you!

If you have any feedback, you can leave comments in the PR and I'll address them in the app!

[marcosfede]

add a funny story

[marcosfede]

test comment

[staging-devin-ai-integration[bot]]

Closing due to inactivity.