Dijkstra's Shortest Path

#include <limits.h>
#include <stdbool.h>
#define V 9

int min_distance(int dist[], bool visited[], int n) {
    int min = INT_MAX, min_idx = -1;
    for (int v = 0; v < n; v++)
        if (!visited[v] && dist[v] <= min) { min = dist[v]; min_idx = v; }
    return min_idx;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V]; bool visited[V];
    for (int i = 0; i < V; i++) { dist[i] = INT_MAX; visited[i] = false; }
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = min_distance(dist, visited, V);
        visited[u] = true;
        for (int v = 0; v < V; v++)
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
}

#include <vector>
#include <queue>
#include <limits>
using namespace std;
typedef pair<int,int> pii;

vector<int> dijkstra(const vector<vector<pii>>& adj, int src) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;          // stale entry
        for (auto [w, v] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
    }
    return dist;
}

import java.util.*;

public static int[] dijkstra(List<List<int[]>> adj, int src) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // {distance, node}
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) continue;
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

import heapq

def dijkstra(adj: list[list[tuple[int,int]]], src: int) -> list[int]:
    n = len(adj)
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]   # (distance, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue    # stale entry
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

function dijkstra(adj, src) {
  const n   = adj.length;
  const dist = new Array(n).fill(Infinity);
  dist[src]  = 0;
  // min-heap: [distance, node]
  const heap = new MinHeap();
  heap.push([0, src]);

  while (!heap.isEmpty()) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue;   // stale entry
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;
}
// Note: JavaScript lacks a built-in MinHeap.
// Use a library or implement one separately.