Эң кыска жолдор: Дейкстра жана Флойд

Салмактуу графта эң кыска жолдор: O(m log n) убакыттагы Дейкстра жана O(n³) убакыттагы Флойд.

Кырларда салмактар (жолдордун узундуктары, нарктар) пайда болгондо BFS иштебей калат. Эки башкы курал: • Дейкстра — бир чокудан баарына чейинки эң кыска жолдор, приоритеттүү кезек менен O(m log n). Чектөөсү: салмактар терс эмес. • Флойд — БАРДЫК түгөйлөрдүн ортосундагы эң кыска жолдор, O(n³), беш сап код. n бир нече жүзгө чейин болгондо жарайт. Дейкстранын идеясы: учурдагы эң жакшы аралыктарды кармап турабыз жана ар дайым ачык чокулардын эң жакынын «жабабыз» — терс эмес салмактарда анын аралыгы мындан ары эч качан жакшырбайт.

Өзүңүз байкап көрүңүз — кодду өзгөртсө болот

#include <iostream>
#include <vector>
#include <queue>

const long long INF = 1e18;

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<std::pair<int, long long>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long w;
        std::cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

std::vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    std::priority_queue<std::pair<long long, int>,
                        std::vector<std::pair<long long, int>>,
                        std::greater<>> pq;
    pq.push({0, 1});

while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > dist[v]) continue; // устаревшая запись - пропускаем

for (auto [to, w] : g[v]) {
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                pq.push({dist[to], to});
            }
        }
    }

for (int v = 1; v <= n; v++) {
        std::cout << "до " << v << ": " << dist[v] << "\n";
    }
    return 0;
}

Киргизүү маалыматтары (мисал — өзгөртсө болот)

Дейкстра. Киргизиңиз: 5 6, андан кийин «a b салмак» кырлары: 1 2 2, 1 3 5, 2 3 1, 2 4 4, 3 5 1, 4 5 3

Негизги сап — if (d > dist[v]) continue: кезекте эскирген жазуулар жатышы мүмкүн (ар бир жакшыртууда чокуну кайра салабыз), аларды үнсүз өткөрүп жиберүү керек. Бул сапсыз алгоритм туура бойдон калат, бирок кыйла жайлап кетиши мүмкүн. Флойд андан да жөнөкөй: үч кабатталган цикл, сырткысы — «аралык» чоку k боюнча. k итерациясынан кийин d[i][j] массиви {1..k} ичинен гана аралык чокуларды колдонгон эң кыска жолдорду сактайт.

Өзүңүз байкап көрүңүз — кодду өзгөртсө болот

Киргизүү маалыматтары (мисал — өзгөртсө болот)

Флойд: бардык түгөйлөр. Киргизиңиз: 4 4, андан кийин: 1 2 5, 2 3 3, 3 4 1, 1 3 10

Терс кырлар үчүн (терс циклдерсиз) O(n·m) убакыттагы Беллман-Форд алгоритми бар — андай маселеге туш болгондо өз алдынча таанышып чыгыңыз. Тапшырма: Дейкстранын мисалында 4-чокуга чейинки аралык 6, ал эми 5-чокуга чейинки 4 экенин жолдорду байкап туруп кол менен текшериңиз. Сабакты өттүм деп белгилеп, минималдуу каркаска өтүңүз.