---
title: "How does Dijkstra's algorithm find the shortest path in a graph?"  
description: "How does Dijkstra's algorithm find the shortest path in a graph?"  
author: "Steilla Mitchel"  
published: 2023-06-13  
updated: 2023-06-16  
canonical: https://www.mindstick.com/forum/158731/how-does-dijkstra-s-algorithm-find-the-shortest-path-in-a-graph  
category: "data structure"  
tags: ["algorithm", "data structure"]  
reading_time: 2 minutes  

---

# How does Dijkstra's algorithm find the shortest path in a graph?

How does Dijkstra's [algorithm](https://www.mindstick.com/blog/119/implementing-cryptography-in-c-sharp-dot-net-by-using-sha1-algorithm) find the shortest [path](https://www.mindstick.com/articles/44333/4-expert-tips-on-how-to-pick-the-right-career-path) in a graph?

## Replies

### Reply by Aryan Kumar

**Dijkstra's algorithm** is an algorithm for finding the shortest paths between nodes in a weighted graph. It works by iteratively adding nodes to a set of visited nodes, starting with the source node. For each node that is added to the set, the algorithm examines all of the nodes that are connected to it and updates the shortest path to those nodes if necessary. The algorithm terminates when all of the nodes in the graph have been visited.

Here is the pseudocode for Dijkstra's algorithm:

Code snippet

```plaintext
function dijkstra(graph, source):
    visited = set()
    dist = {}
    for node in graph.nodes:
        dist[node] = float("inf")
    dist[source] = 0

    while visited != graph.nodes:
        node = min(graph.nodes, key=dist.get)
        visited.add(node)
        for neighbor in graph.get_neighbors(node):
            new_dist = dist[node] + graph.get_edge_weight(node, neighbor)
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist

    return dist
```

Here is an explanation of the pseudocode:

- The `visited` set keeps track of the nodes that have already been visited.
- The `dist` dictionary maps from nodes to their distances from the source node.
- The `min` function is used to find the node with the shortest distance that has not yet been visited.
- The `for` loop iterates over all of the nodes in the graph.
- The `if` statement checks if the node has not already been visited.
- The `new_dist` variable is the distance from the current node to the neighbor.
- The `dist[neighbor]` variable is the current distance from the source node to the neighbor.
- The `if` statement checks if the new distance is shorter than the current distance.
- If the new distance is shorter, the `dist[neighbor]` variable is updated with the new distance.
- The `return` statement returns the `dist` dictionary.

Dijkstra's algorithm is a greedy algorithm. This means that it always chooses the node with the shortest distance that has not yet been visited. This guarantees that the algorithm will find the shortest path to the destination node.

Dijkstra's algorithm is a versatile algorithm that can be used to solve a variety of problems. For example, it can be used to find the shortest path between two cities, the shortest route to deliver a package, or the shortest path to connect a network of computers.


---

Original Source: https://www.mindstick.com/forum/158731/how-does-dijkstra-s-algorithm-find-the-shortest-path-in-a-graph

Copyright © MindStick Software Pvt. Ltd. This Markdown version is provided for developers, AI systems, and offline reading.