Алгоритмы на графах: MST и кратчайшие пути — Блог
$ cat learn/04-graph-algorithms.md

Алгоритмы на графах: MST и кратчайшие пути

Алгоритмы MST Dijkstra Bellman-Ford Floyd-Warshall Кратчайший путь

Алгоритмы на графах: MST и кратчайшие пути

История

Минимальное остовное дерево (MST):

  • 1927 — Оскар Борувка предложил первый алгоритм для MST
  • 1957 — Прим опубликовал свой алгоритм
  • 1956 — Краскал опубликовал альтернативный алгоритм (использует DSU/Union-Find)

Кратчайшие пути:

  • 1956 — Эдсгер Дейкстра предложил алгоритм для кратчайшего пути из одной вершины
  • 1958 — Форд и Беллман обобщили для графов с отрицательными весами
  • 1962 — Флойд предложил алгоритм для всех пар

Реальные примеры

MST: прокладка кабеля между городами

Задача: соединить все города минимальным кабелем

    4      3
 A ───── B ───── C
 │   2  │   1  │
 │      │     │
 D ───── E ──── F
    4      2

Выбор рёбер:
A-D (2) → A-B (4) → B-C (1) → E-F (2) → B-E (3)
Общая длина: 12

Минимальное остовное дерево:
    4      3
 A ───── B ── C
 │
 │      (E)────F
 D ───── E

Dijkstra: навигатор (GPS)

Маршрут из точки A в точку F:

    A──2──B──1──F
    │   │      │
    4  3      2
    │   │      │
    D──1──C──2──E

Кратчайший путь: A→B→F (длина: 2+1=3)
Альтернатива:   A→D→C→E→F (длина: 4+1+2+2=9)
Альтернатива:   A→B→C→E→F (длина: 2+3+2+2=9)

Bellman-Ford: арбитраж валют

Курсы валют (можно заработать на разнице):

USD → EUR: 0.85
EUR → GBP: 0.75
GBP → USD: 1.6

Путь: USD → EUR → GBP → USD
Доход: 1 × 0.85 × 0.75 × 1.6 = 1.02 (2% прибыль!)

Отрицательный цикл = возможность заработать

Алгоритмы MST

Prim Algorithm (1957)

Идея: Начинаем с одной вершины, каждый раз добавляем ближайшую.

Граф:
    7      5
 A ───── B ───── C
 │   5  │   7  │
 │      │     │
 D ───── E ──── F
    4      2

Шаг 1: Начинаем с A
       [A]  расстояния: B=7, D=4

Шаг 2: Добавляем ближайшее: D
       [A,D]  расстояния: B=7, E=4

Шаг 3: Добавляем ближайшее: E
       [A,D,E]  B=5, F=2

Шаг 4: Добавляем ближайшее: F
       [A,D,E,F]  B=5, C=7

Шаг 5: Добавляем B
       [A,D,E,F,B]  C=5

Шаг 6: Добавляем C

MST: A-D(4), D-E(4), E-F(2), B-E(3), B-C(5) = 18

// prim.c
void prim(MGraph *G, int start) {
    int visited[MAXVERNUM] = {0};
    int dist[MAXVERNUM];
    
    // Инициализация
    for (int i = 0; i < G->numVertexes; i++) {
        dist[i] = INFINITY;
    }
    dist[start] = 0;
    
    for (int count = 0; count < G->numVertexes; count++) {
        // Найти непосещенную вершину с минимальным расстоянием
        int minDist = INFINITY, v = -1;
        for (int i = 0; i < G->numVertexes; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                v = i;
            }
        }
        
        visited[v] = 1;
        printf("%c ", G->vexs[v]);
        
        // Обновить расстояния до соседей
        for (int i = 0; i < G->numVertexes; i++) {
            if (!visited[i] && G->edges[v][i] < dist[i]) {
                dist[i] = G->edges[v][i];
            }
        }
    }
}

Kruskal Algorithm (1956)

Идея: Сортируем все рёбра по весу, добавляем если не создаёт цикл.

Граф:
    7      5
 A ───── B ───── C
 │   5  │   7  │
 │      │     │
 D ───── E ──── F
    4      2

Сортируем рёбра по весу:
E-F (2)  ✓ добавили
D-E (4)  ✓ добавили  
A-D (4)  ✓ добавили
A-B (5)  ✓ добавили
B-C (5)  ✓ добавили (цикл!)

// kruskal.c
typedef struct {
    int from, to, weight;
} Edge;

int comp(const void *a, const void *b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

// DSU (Disjoint Set Union)
/parent[x] = корень множества, содержащего x
// find(x) = найти корень (с compression)
// union(x, y) = объединить множества

int find(int x, int parent[]) {
    if (parent[x] != x) {
        parent[x] = find(parent[x], parent);
    }
    return parent[x];
}

void union_sets(int x, int y, int parent[], int rank[]) {
    x = find(x, parent);
    y = find(y, parent);
    if (x == y) return;
    
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else if (rank[x] > rank[y]) {
        parent[y] = x;
    } else {
        parent[y] = x;
        rank[x]++;
    }
}

void kruskal(MGraph *G) {
    // Собрать все рёбра
    Edge edges[MAXVERNUM * MAXVERNUM];
    int m = 0;
    for (int i = 0; i < G->numVertexes; i++) {
        for (int j = i + 1; j < G->numVertexes; j++) {
            if (G->edges[i][j] != INFINITY && G->edges[i][j] != 0) {
                edges[m++] = (Edge){i, j, G->edges[i][j]};
            }
        }
    }
    
    // Сортировать по весу
    qsort(edges, m, sizeof(Edge), comp);
    
    // DSU
    int parent[MAXVERNUM], rank[MAXVERNUM] = {0};
    for (int i = 0; i < G->numVertexes; i++) {
        parent[i] = i;
    }
    
    // Добавляем рёбра
    int count = 0;
    for (int i = 0; i < m && count < G->numVertexes - 1; i++) {
        int u = find(edges[i].from, parent);
        int v = find(edges[i].to, parent);
        
        if (u != v) {
            union_sets(u, v, parent, rank);
            printf("%c - %c: %d\n",
                   G->vexs[edges[i].from],
                   G->vexs[edges[i].to],
                   edges[i].weight);
            count++;
        }
    }
}

Prim vs Kruskal

ХарактеристикаPrimKruskal
СтруктураПриоритетная очередьUnion-Find
СложностьO(V²) или O(E log V)O(E log E)
ТипЖадныйЖадный
РезультатОдин MSTОдин MST

Алг��ритмы кратчайшего пути

Dijkstra (1956)

Идея: Жадный алгоритм, работает только с неотрицательными весами.

Граф:
    A──2──B──1──F
    │   │      │
    4  3      2
    │   │      │
    D──1──C──2──E

Ищем кратчайший путь из A во все вершины:

Шаг 1: dist[A] = 0, others = ∞
       A:0  B:2  C:∞  D:4  E:∞  F:∞

Шаг 2: Из A в B (2), D (4)
       A:0  B:2  C:∞  D:4  E:∞  F:∞

Шаг 3: Берем B (минимальный)
       A:0  B:2✓ C:3  D:4  E:∞  F:3

Шаг 4: Берем C или F (3)
       A:0  B:2✓ C:3✓ D:4  E:5  F:3✓

Шаг 5: Берем F (3)
       A:0  B:2✓ C:3✓ D:4  E:5  F:3✓

Результат:
A→B: 2, A→C: 3, A→D: 4, A→E: 5, A→F: 3

// dijkstra.c
void dijkstra(MGraph *G, int start) {
    int dist[MAXVERNUM];
    int visited[MAXVERNUM] = {0};
    
    for (int i = 0; i < G->numVertexes; i++) {
        dist[i] = INFINITY;
    }
    dist[start] = 0;
    
    for (int count = 0; count < G->numVertexes; count++) {
        // Найти вершину с минимальным расстоянием
        int minDist = INFINITY, v = -1;
        for (int i = 0; i < G->numVertexes; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                v = i;
            }
        }
        
        visited[v] = 1;
        
        // Обновить расстояния
        for (int i = 0; i < G->numVertexes; i++) {
            if (!visited[i] &&
                G->edges[v][i] != INFINITY &&
                G->edges[v][i] != 0 &&
                dist[v] + G->edges[v][i] < dist[i]) {
                dist[i] = dist[v] + G->edges[v][i];
            }
        }
    }
    
    // Вывод
    for (int i = 0; i < G->numVertexes; i++) {
        printf("%c: %d\n", G->vexs[i], dist[i]);
    }
}

Bellman-Ford (1958)

Идея: Динамическое программирование, работает с отрицательными весами.

Граф с отрицательным ребром:
    A──(-2)──B──3──C

    A→B = -2
    B→C = 3
    A→C прямой = 6

Проверяем:
Шаг 1: A→B = -2
Шаг 2: A→C = A→B + B→C = -2 + 3 = 1 < 6 ✓

// bellman-ford.c
void bellman_ford(MGraph *G, int start) {
    int dist[MAXVERNUM];
    
    for (int i = 0; i < G->numVertexes; i++) {
        dist[i] = INFINITY;
    }
    dist[start] = 0;
    
    // Повторяем V-1 раз
    for (int k = 0; k < G->numVertexes - 1; k++) {
        for (int u = 0; u < G->numVertexes; u++) {
            for (int v = 0; v < G->numVertexes; v++) {
                if (G->edges[u][v] != INFINITY &&
                    G->edges[u][v] != 0 &&
                    dist[u] != INFINITY &&
                    dist[u] + G->edges[u][v] < dist[v]) {
                    dist[v] = dist[u] + G->edges[u][v];
                }
            }
        }
    }
    
    // Проверка на отрицательный цикл
    for (int u = 0; u < G->numVertexes; u++) {
        for (int v = 0; v < G->numVertexes; v++) {
            if (G->edges[u][v] != INFINITY &&
                G->edges[u][v] != 0 &&
                dist[u] != INFINITY &&
                dist[u] + G->edges[u][v] < dist[v]) {
                printf("Отрицательный цикл обнаружен!\n");
                return;
            }
        }
    }
    
    for (int i = 0; i < G->numVertexes; i++) {
        printf("%c: %d\n", G->vexs[i], dist[i]);
    }
}

Dijkstra vs Bellman-Ford

ХарактеристикаDijkstraBellman-Ford
Веса≥ 0любые
СложностьO(V²) или O(E log V)O(V × E)
Отрицательные циклы❌✓ detection
Отрицательные рёбра✓✓

Floyd-Warshall (1962)

Идея: Динамическое программирование для всех пар.

d[i][j] = минимальный путь через промежуточные вершины

// floyd-warshall.c
void floyd_warshall(int n, int graph[][MAXVERNUM]) {
    // dp[i][j] = минимальное расстояние i → j
    int dp[MAXVERNUM][MAXVERNUM];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = graph[i][j];
        }
    }
    
    // Через каждую промежуточную вершину k
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][k] != INFINITY &&
                    dp[k][j] != INFINITY &&
                    dp[i][k] + dp[k][j] < dp[i][j]) {
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }
    
    // Вывод матрицы
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
}

Пример Floyd-Warshall

Граф:
A B C
- - -
0 4 9
3 0 ∞
∞ 5 0

Матрица смежности:
    A   B   C
A   0   4   9
B   3   0   5
C  ∞   5   0

k = A: проверяем пути через A
- B→C = min(5, 3+9=12) = 5
- C→B = min(5, 9+4=13) = 5

k = B: проверяем пути через B
- A→C = min(9, 4+5=9) = 9
- C→A = min(∞, 5+3=8) = 8

Результат:
    A   B   C
A   0   4   8
B   3   0   5
C   8   5   0

Сравнение алгоритмов

АлгоритмНазначениеСложностьОграничения
PrimMSTO(V²) или O(E log V)нет
KruskalMSTO(E log E)нет
Dijkstra1-to-allO(V²)веса ≥ 0
Bellman-Ford1-to-allO(V × E)нет (detects negative cycle)
Floyd-Warshallall-to-allO(V³)нет

Реальные применения

MST

  • Прокладка дорог, кабелей, трубопроводов
  • Кластеризация данных
  • Сетевая маршрутизация (протоколы RIP, OSPF)

Кратчайшие пути

  • GPS навигация
  • Маршрутизация пакетов (BGP, OSPF)
  • Планирование маршрутов доставки

Floyd-Warshall

  • Кратчайшие пути между всеми парами
  • Транзитивное замыкание
  • Анализ социальных сетей

Ключевые выводы

  1. Prim + Kruskal — оба дают MST, выбирайте по плотности графа

  2. Dijkstra — быстрее, но только для неотрицательных весов

  3. Bellman-Ford — медленнее, но обнаруживает отрицательные циклы

  4. Floyd-Warshall — для всех пар, O(V³) памяти

  5. Все эти алгоритмы — жадные (Prim, Dijkstra) или динамическое программирование (Bellman-Ford, Floyd-Warshall)

← Все статьи