Поиск кратчайшего пути между двумя узлами графа — распространенная проблема в информатике. Одним из популярных алгоритмов решения этой проблемы является алгоритм Дейкстры, который гарантирует нахождение кратчайшего пути в графах с неотрицательными весами ребер. В этой статье блога мы рассмотрим несколько методов реализации алгоритма Дейкстры на языке программирования C, а также приведем примеры кода.

Метод 1: Представление в матрице смежности
Первый метод включает представление графа с использованием матрицы смежности. Матрица смежности представляет собой двумерный массив, где каждая запись представляет вес ребра между двумя узлами. Вот пример фрагмента кода:

#define INF 9999
#define V 6
void dijkstra(int graph[V][V], int src) {
    // Initialize distance array
    int dist[V];
    bool sptSet[V];
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        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] != INF && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        }
    }
// Print the shortest distances
    printSolution(dist, V);
}

Метод 2: Представление списка смежности
Другой метод предполагает использование списка смежности для представления графа. В этом представлении каждый узел хранит список соседних узлов и соответствующие веса ребер. Вот пример фрагмента кода:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define INF 9999
struct Node {
    int dest;
    int weight;
    struct Node* next;
};
struct Graph {
    int V;
    struct Node adjLists;
};
struct Node* createNode(int dest, int weight) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjLists = (struct Node)malloc(V * sizeof(struct Node*));
    for (int i = 0; i < V; i++)
        graph->adjLists[i] = NULL;
    return graph;
}
void addEdge(struct Graph* graph, int src, int dest, int weight) {
    struct Node* newNode = createNode(dest, weight);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}
void dijkstra(struct Graph* graph, int src) {
    int dist[graph->V];
    bool sptSet[graph->V];
    for (int i = 0; i < graph->V; i++) {
        dist[i] = INF;
        sptSet[i] = false;
    }
    dist[src] = 0;
    for (int count = 0; count < graph->V - 1; count++) {
        int u = minDistance(dist, sptSet, graph->V);
        sptSet[u] = true;
        struct Node* temp = graph->adjLists[u];
        while (temp != NULL) {
            int v = temp->dest;
            if (!sptSet[v] && dist[u] != INF && dist[u] + temp->weight < dist[v])
                dist[v] = dist[u] + temp->weight;
            temp = temp->next;
        }
    }
// Print the shortest distances
    printSolution(dist, graph->V);
}

В этой статье мы исследовали два разных метода реализации алгоритма Дейкстры на C: один с использованием матрицы смежности, а другой с использованием списка смежности. Оба метода можно использовать для эффективного поиска кратчайшего пути в графе. В зависимости от размера и характеристик графа один метод может оказаться более подходящим, чем другой. Понимая эти реализации, вы сможете решать различные проблемы поиска пути с помощью алгоритма Дейкстры на языке C.