Dijkstra's Algorithm

def dijkstra(graph, start):
    #Initialize - start node should be assgined '0' and all other nodes - infinity
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    visited = set()
 
    while len(visited) < len(graph):
        #For the next selection - find the unvisited node with the smallest cumulative distance so far
        current_node = min((node for node in graph if node not in visited), key=lambda x: distances[x])
 
        #Then update the distance for the neighbours of the currently selection node
        for neighbor, weight in graph[current_node].items():
            distance = distances[current_node] + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
 
        visited.add(current_node)
 
    return distances
 
graph = {
    'A': {'B': 1, 'C': 2},
    'B': {'A': 1, 'C': 3, 'D': 3, 'E': 4},
    'C': {'A': 2, 'B': 3, 'E': 5},
    'D': {'B': 3, 'E': 3, 'F': 4},
    'E': {'C': 5, 'B': 4, 'D': 3, 'F': 1},
    'F': {'D': 4, 'E': 1},
}
 
start_node = 'A'
result = dijkstra(graph, start_node)
print(f"Shortest distances from node {start_node}: {result}")
 
 

function dijkstra(graph, start) {
    const distances = {};
    const visited = new Set();
 
    // Initialize - start node should be assgined '0' and all other nodes - infinity
    for (const node in graph) {
        distances[node] = node === start ? 0 : Infinity;
    }
 
    while (visited.size < Object.keys(graph).length) {
        let current = null;
        
        // For the next selection - find the unvisited node with the smallest cumulative distance so far
        for (const node in graph) {
            if (!visited.has(node) && (current === null || distances[node] < distances[current])) {
                current = node;
            }
        }
 
        // Then update the distance for the neighbours of the currently selection node
        for (const neighbor in graph[current]) {
            const distance = distances[current] + graph[current][neighbor];
            if (distance < distances[neighbor]) {
                distances[neighbor] = distance;
            }
        }
 
        visited.add(current);
    }
 
    return distances;
}
 
// Example usage:
const graph = {
    'A': {'B': 1, 'C': 2},
    'B': {'A': 1, 'C': 3, 'D': 3, 'E': 4},
    'C': {'A': 2, 'B': 3, 'E': 5},
    'D': {'B': 3, 'E': 3, 'F': 4},
    'E': {'C': 5, 'B': 4, 'D': 3, 'F': 1},
    'F': {'D': 4, 'E': 1},
};
 
const startNode = 'A';
const result = dijkstra(graph, startNode);
console.log(`Shortest distances from node ${startNode}:`, result);
 

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
 
public class DijkstraAlgorithm {
 
    public static Map<String, Integer> dijkstra(Map<String, Map<String, Integer>> graph, String start) {
        Map<String, Integer> distances = new HashMap<>();
        Set<String> visited = new HashSet<>();
 
        // Initialize - start node should be assgined '0' and all other nodes - infinity
        for (String node : graph.keySet()) {
            distances.put(node, node.equals(start) ? 0 : Integer.MAX_VALUE);
        }
 
        while (visited.size() < graph.size()) {
            String current = null;
 
            // For the next selection - find the unvisited node with the smallest cumulative distance so far
            for (String node : graph.keySet()) {
                if (!visited.contains(node) && (current == null || distances.get(node) < distances.get(current))) {
                    current = node;
                }
            }
 
            // Then update the distance for the neighbours of the currently selection node
            for (Map.Entry<String, Integer> entry : graph.get(current).entrySet()) {
                String neighbor = entry.getKey();
                int weight = entry.getValue();
                int distance = distances.get(current) + weight;
 
                if (distance < distances.get(neighbor)) {
                    distances.put(neighbor, distance);
                }
            }
 
            visited.add(current);
        }
 
        return distances;
    }
 
    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = new HashMap<>();
        graph.put("A", Map.of("B", 1, "C", 2));
        graph.put("B", Map.of("A", 1, "C", 3, "D", 3, "E", 4));
        graph.put("C", Map.of("A", 2, "B", 3, "E", 5));
        graph.put("D", Map.of("B", 3, "E", 3, "F", 4));
        graph.put("E", Map.of("C", 5, "B", 4, "D", 3, "F", 1));
        graph.put("F", Map.of("D", 4, "E", 1));
 
        String startNode = "A";
        Map<String, Integer> result = dijkstra(graph, startNode);
        System.out.println("Shortest distances from node " + startNode + ": " + result);
    }
}
 
 
 

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
#define MAX_NODES 6
 
void dijkstra(int graph[MAX_NODES][MAX_NODES], int start, int distances[MAX_NODES]) {
    int visited[MAX_NODES] = {0};
 
    // Initialize - start node should be assgined '0' and all other nodes - infinity
    for (int i = 0; i < MAX_NODES; i++) {
        distances[i] = (i == start) ? 0 : INT_MAX;
    }
 
    for (int count = 0; count < MAX_NODES - 1; count++) {
        // For the next selection - find the unvisited node with the smallest cumulative distance so far
        int minDistance = INT_MAX, minIndex;
 
        for (int i = 0; i < MAX_NODES; i++) {
            if (!visited[i] && distances[i] < minDistance) {
                minDistance = distances[i];
                minIndex = i;
            }
        }
 
        visited[minIndex] = 1;
 
        // Then update the distance for the neighbours of the currently selection node
        for (int i = 0; i < MAX_NODES; i++) {
            if (!visited[i] && graph[minIndex][i] && (distances[minIndex] != INT_MAX) &&
                (distances[minIndex] + graph[minIndex][i] < distances[i])) {
                distances[i] = distances[minIndex] + graph[minIndex][i];
            }
        }
    }
}
 
int main() {
    // 
    int graph[MAX_NODES][MAX_NODES] = {
        // A, B, C, D, E, F
        {0, 1, 2, 0, 0, 0}, // A
        {1, 0, 3, 3, 4, 0}, // B
        {2, 3, 0, 0, 5, 0}, // C
        {0, 3, 0, 0, 3, 4}, // D
        {0, 4, 5, 3, 0, 1}, // E
        {0, 0, 0, 4, 1, 0}  // F
    };
 
    int startNode = 0;
    int distances[MAX_NODES];
 
    dijkstra(graph, startNode, distances);
 
    printf("Shortest distances from node %d:\n", startNode);
    for (int i = 0; i < MAX_NODES; i++) {
        printf("To node %d: %d\n", i, distances[i]);
    }
 
    return 0;
}
 

<?php
 
function dijkstra($graph, $start)
{
    $distances = [];
    $visited = [];
 
    // Initialize - start node should be assgined '0' and all other nodes - infinity
    foreach ($graph as $node => $neighbors) {
        $distances[$node] = ($node === $start) ? 0 : INF;
        $visited[$node] = false;
    }
 
    while (count(array_filter($visited)) < count($graph)) {
        $current = null;
 
        // For the next selection - find the unvisited node with the smallest cumulative distance so far
        foreach ($graph as $node => $neighbors) {
            if (!$visited[$node] && ($current === null || $distances[$node] < $distances[$current])) {
                $current = $node;
            }
        }
 
        // Then update the distance for the neighbours of the currently selection node
        foreach ($graph[$current] as $neighbor => $weight) {
            $distance = $distances[$current] + $weight;
            if ($distance < $distances[$neighbor]) {
                $distances[$neighbor] = $distance;
            }
        }
 
        $visited[$current] = true;
    }
 
    return $distances;
}
 
 
$graph = [
    'A' => ['B' => 1, 'C' => 2],
    'B' => ['A' => 1, 'C' => 3, 'D' => 3, 'E' => 4],
    'C' => ['A' => 2, 'B' => 3, 'E' => 5],
    'D' => ['B' => 3, 'E' => 3, 'F' => 4],
    'E' => ['C' => 5, 'B' => 4, 'D' => 3, 'F' => 1],
    'F' => ['D' => 4, 'E' => 1],
];
 
$startNode = 'A';
$result = dijkstra($graph, $startNode);
echo "Shortest distances from node $startNode:\n";
foreach ($result as $node => $distance) {
    echo "To node $node: $distance\n";
}