Add Dijkstra's Algorithm for Shortest Paths

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

Implementation of Graph Algorithms: Dijkstra's Shortest Path and Longest Simple Path

This pull request adds implementations of two graph algorithms to the algorithms repository:

1. Dijkstra's algorithm for finding the shortest paths in a weighted graph
2. A new algorithm for finding the longest simple path in a weighted graph

Features

• Efficient implementation of Dijkstra's algorithm using a priority queue (heapq)
• Novel implementation of a longest simple path algorithm using depth-first search (DFS)
• Functions to reconstruct paths and calculate total weights
• Comprehensive test cases for both algorithms
• Example usage demonstrating the functionality of both algorithms

Implementation Details

Dijkstra's Algorithm

The implementation consists of two main functions:

1. dijkstra(graph, start): Computes the shortest distances from the start node to all other nodes in the graph.
2. get_path(previous, start, end): Reconstructs the shortest path between two nodes using the result from the Dijkstra function.

Longest Simple Path Algorithm

The implementation uses a depth-first search approach:

1. longest_simple_path(graph): Finds the longest simple path (without repeating nodes) in the weighted graph.
2. An internal DFS function explores all possible paths and keeps track of the longest one found.

Complexity Analysis

• Dijkstra's Algorithm: O((V + E) log V) time complexity, where V is the number of vertices and E is the number of edges.
• Longest Simple Path: O(n!) time complexity in the worst case, where n is the number of nodes. Space complexity is O(n) for the recursion stack.

Test Cases

Both algorithms include multiple test cases:

1. Simple connected graphs to verify correct calculations and path reconstruction.
2. Special case graphs (e.g., linear graphs, disconnected graphs) to ensure proper handling of edge cases.

Example Usage

Example usage is provided in the __main__ section of both algorithm files, demonstrating how to use the algorithms with sample graphs.

Compliance with Contributing Guidelines

• Implemented in Python 3
• Clean and understandable code with proper comments and explanations
• Test cases included for both algorithms
• Example usage provided for both algorithms

Link to Devin Run

https://staging.itsdev.in/devin/81a084cbce10447791d72f784cadc81c

These implementations aim to provide clear and efficient solutions for finding both shortest paths and longest simple paths in weighted graphs. The longest simple path algorithm, in particular, offers a unique addition to the repository, as it solves a less common but equally interesting graph problem.

This Devin run was requested by Federico.

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

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

If you have any feedback, you can leave comments here and I'll address them!

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

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

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

Closing due to inactivity.