Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Алгоритм Дейкстры на C

Вычисляйте кратчайшие расстояния от одной вершины в графе с неотрицательными весами.

Расстояние до начальной вершины равно нулю, остальные сначала неизвестны или бесконечны. Выбирайте непосещённую вершину с наименьшим расстоянием и проверяйте её рёбра: если путь через неё короче, обновляйте расстояние.

Алгоритм требует неотрицательных весов. Различайте отсутствие ребра и ребро нулевого веса согласно принятому представлению. Не прибавляйте вес к значению-бесконечности и проверяйте переполнение при расширении диапазона.

Вариант с матрицей и линейным выбором вершины обычно работает за O(V²). Проверьте несвязные вершины и альтернативные пути. Для отрицательных весов нужен другой алгоритм.

Код C

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define V 5

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Vertex 	 Distance from Source (%d)\n", src);
    for (int i = 0; i < V; i++) printf("%d 		 %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 8, 0},
        {4, 0, 8, 11, 0},
        {0, 8, 0, 7, 2},
        {8, 11, 7, 0, 9},
        {0, 0, 2, 9, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

Открыть в компиляторе

Ожидаемый вывод

Vertex 	 Distance from Source (0)
0 		 0
1 		 4
2 		 12
3 		 8
4 		 14

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.