Single-source shortest path problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between two vertices on a graph.

The algorithm maintains a set of visited vertices and a set of unvisited vertices. It starts at the source vertex and iteratively selects the unvisited vertex with the smallest tentative distance from the source. It then visits the neighbors of this vertex and updates their tentative distances if a shorter path is found. This process continues until the destination vertex is reached, or all reachable vertices are visited.

In a directed graph, each edge has a direction, indicating the direction of travel between the vertices connected by the edge. In this case, the algorithm follows the direction of the edges when searching for the shortest path.

In an undirected graph, the edges have no direction, and the algorithm can traverse both forward and backward along the edges when searching for the shortest path.

Python

def dijkstra(self, start):
    distances = {vertex: float('infinity') for vertex in self.graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in self.graph[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

C++

class Graph {
    unordered_map<char, vector<pair<char, int>>> graph;

public:
    void add_edge(char u, char v, int w) {
        graph[u].push_back({v, w});
    }

    unordered_map<char, int> dijkstra(char start) {
        unordered_map<char, int> distances;
        for (auto& pair : graph) {
            distances[pair.first] = INT_MAX;
        }
        distances[start] = 0;

        priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            char current_vertex = pq.top().second;
            int current_distance = pq.top().first;
            pq.pop();

            if (current_distance > distances[current_vertex]) {
                continue;
            }

            for (auto& neighbor : graph[current_vertex]) {
                int distance = current_distance + neighbor.second;
                if (distance < distances[neighbor.first]) {
                    distances[neighbor.first] = distance;
                    pq.push({distance, neighbor.first});
                }
            }
        }

        return distances;
    }
};