האלגוריתם של Dijkstra (דייקסטרה)

1import heapq2
3
4def dijkstra(graph, start):5    dist = {node: float("inf") for node in graph}6    dist[start] = 07    pq = [(0, start)]8    while pq:9        d, node = heapq.heappop(pq)10        if d > dist[node]:11            continue  # stale entry, a shorter path was already found12        for neighbor, weight in graph[node]:13            new_dist = d + weight14            if new_dist < dist[neighbor]:15                dist[neighbor] = new_dist16                heapq.heappush(pq, (new_dist, neighbor))17    return dist18
19
20graph = {21    "A": [("B", 4), ("C", 1)],22    "B": [("D", 1)],23    "C": [("B", 2), ("D", 5)],24    "D": [("E", 3)],25    "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29    print(f"A -> {node}: {d}")

1const graph = {2    A: { B: 4, C: 2 },3    B: { C: 5, D: 10 },4    C: { E: 3 },5    D: { F: 11 },6    E: { D: 4 },7    F: {},8};9
10function dijkstra(source) {11    const dist = {};12    const visited = new Set();13    for (const node in graph) dist[node] = Infinity;14    dist[source] = 0;15    while (visited.size < Object.keys(graph).length) {16        // JS has no built-in heap: linear scan for the closest node (O(V^2))17        let u = null;18        for (const node in dist) {19            if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20                u = node;21            }22        }23        if (dist[u] === Infinity) break;24        visited.add(u);25        for (const [v, w] of Object.entries(graph[u])) {26            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27        }28    }29    return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7    public static void main(String[] args) {8        int n = 6;9        List<List<int[]>> adj = new ArrayList<>();10        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11        int[][] edges = {12            {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13            {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14        };15        for (int[] e : edges) {16            adj.get(e[0]).add(new int[]{e[1], e[2]});17            adj.get(e[1]).add(new int[]{e[0], e[2]});18        }19
20        int[] dist = new int[n];21        Arrays.fill(dist, Integer.MAX_VALUE);22        dist[0] = 0;23        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24        pq.add(new int[]{0, 0}); // {node, distance}25        while (!pq.isEmpty()) {26            int[] cur = pq.poll();27            int node = cur[0], d = cur[1];28            if (d > dist[node]) continue; // stale queue entry29            for (int[] edge : adj.get(node)) {30                int next = edge[0], nd = d + edge[1];31                if (nd < dist[next]) {32                    dist[next] = nd;33                    pq.add(new int[]{next, nd});34                }35            }36        }37        System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38    }39}

1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6    const int INF = 1000000000;7    // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8    std::vector<std::vector<std::pair<int, int>>> adj = {9        {{1, 4}, {2, 1}},  // 010        {{3, 1}},          // 111        {{1, 2}, {3, 5}},  // 212        {{4, 3}},          // 313        {},                // 414    };15    int n = static_cast<int>(adj.size());16    std::vector<int> dist(n, INF);17    dist[0] = 0;18    using State = std::pair<int, int>;  // (distance, node)19    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20    pq.push({0, 0});21    while (!pq.empty()) {22        auto [d, u] = pq.top();23        pq.pop();24        if (d > dist[u]) continue;  // stale queue entry25        for (auto [v, w] : adj[u]) {26            if (d + w < dist[v]) {27                dist[v] = d + w;28                pq.push({dist[v], v});29            }30        }31    }32    for (int v = 0; v < n; ++v) {33        std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34    }35    return 0;36}

1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8    // Weighted directed graph: w[u][v] = 0 means no edge9    int w[N][N] = {10        {0, 4, 1, 0, 0},11        {0, 0, 0, 1, 0},12        {0, 2, 0, 5, 0},13        {0, 0, 0, 0, 3},14        {0, 0, 0, 0, 0},15    };16    int dist[N];17    bool done[N] = {false};18    for (int v = 0; v < N; v++) dist[v] = INF;19    dist[0] = 0;20    // O(V^2) scan for the closest unfinished node (no heap needed here)21    for (int iter = 0; iter < N; iter++) {22        int u = -1;23        for (int v = 0; v < N; v++) {24            if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25        }26        if (dist[u] == INF) break;  // remaining nodes are unreachable27        done[u] = true;28        for (int v = 0; v < N; v++) {29            if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30                dist[v] = dist[u] + w[u][v];31            }32        }33    }34    for (int v = 0; v < N; v++) {35        printf("Distance 0 -> %d: %d\n", v, dist[v]);36    }37    return 0;38}