Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Dijkstra's algorithm #70

Open
Invincible1602 opened this issue Oct 3, 2024 · 1 comment · May be fixed by #103
Open

Dijkstra's algorithm #70

Invincible1602 opened this issue Oct 3, 2024 · 1 comment · May be fixed by #103
Assignees
@mukprabhakar @Invincible1602
Labels
hacktoberfest

Comments

@Invincible1602
Copy link

Hey @DhanushNehru,

I want to implement the Dijkstra's Algorithm in Python.
Dijkstra's algorithm is a greedy algorithm that finds the shortest paths in a graph with non-negative edge weights by following these steps:

  • Initialize the distance to the source vertex as 0 and to all other vertices as infinity.
  • Use a priority queue (min-heap) to select the vertex with the smallest distance that has not yet been processed.
  • For the selected vertex, check all of its adjacent vertices. For each adjacent vertex, calculate the tentative distance from the source
    vertex through the selected vertex. If this tentative distance is smaller than the currently known distance, update the shortest distance.
    Repeat this process until all vertices have been processed.

Input:

  • A connected, weighted graph represented as an adjacency list, where the keys represent vertices and the values represent dictionaries of neighboring vertices with their edge weights.
  • The source vertex from which the shortest paths are to be calculated.

Output:

  • A dictionary representing the shortest distances from the source vertex to all other vertices in the graph.

Please assign me the issue and hacktoberfest label.
This was referenced Oct 5, 2024
Closed
Open
@mukprabhakar
Copy link
Contributor

Python implementation of Dijkstra's Algorithm using a priority queue (min-heap) to find the shortest path in a graph with non-negative edge weights:
import heapq

def dijkstra(graph, source):
# Initialize the priority queue
priority_queue = []

# Initialize distances to infinity for all vertices except the source
distances = {vertex: float('infinity') for vertex in graph}
distances[source] = 0

# Push the source node into the priority queue with distance 0
heapq.heappush(priority_queue, (0, source))

while priority_queue:
    # Pop the vertex with the smallest distance
    current_distance, current_vertex = heapq.heappop(priority_queue)
    
    # If the current distance is greater than the recorded distance, skip it
    if current_distance > distances[current_vertex]:
        continue
    
    # Check adjacent vertices
    for neighbor, weight in graph[current_vertex].items():
        distance = current_distance + weight
        
        # Only consider this path if it's better than the known one
        if distance < distances[neighbor]:
            distances[neighbor] = distance
            # Push the updated distance and neighbor into the queue
            heapq.heappush(priority_queue, (distance, neighbor))

return distances

Example usage:
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}

source = 'A'
shortest_distances = dijkstra(graph, source)
print(shortest_distances)
Output:
{
'A': 0,
'B': 1,
'C': 3,
'D': 4
}
Explanation:
Priority Queue (min-heap) is used to efficiently fetch the vertex with the smallest tentative distance.
Distances Dictionary is initialized with infinity for all vertices except the source, which starts with a distance of 0.
Relaxation Process checks each neighbor of the currently selected vertex, updating distances if a shorter path is found.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mukprabhakar mukprabhakar

@Invincible1602 Invincible1602

Labels
hacktoberfest
Projects
None yet
Milestone
No milestone
3 participants
@DhanushNehru @mukprabhakar @Invincible1602