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

// Упрощенная схема работы алгоритма Дейкстры
1. Установить расстояние до стартовой вершины = 0, до остальных = ∞
2. Пометить все вершины как непосещенные
3. Пока есть непосещенные вершины:
   a. Выбрать непосещенную вершину с наименьшим расстоянием
   b. Пометить её как посещенную
   c. Для каждого соседа этой вершины:
      i. Рассчитать новое расстояние через текущую вершину
      ii. Если новое расстояние меньше известного, обновить его

function Dijkstra(Graph, source):
    // Инициализация
    for each vertex v in Graph:
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        visited[v] ← false
    dist[source] ← 0
    
    // Основной цикл
    while exists unvisited vertices:
        u ← vertex with minimum dist[] among unvisited
        if dist[u] = INFINITY:
            break  // Остальные вершины недостижимы
        visited[u] ← true
        
        // Релаксация рёбер
        for each neighbor v of u:
            if !visited[v]:
                alt ← dist[u] + weight(u, v)
                if alt < dist[v]:
                    dist[v] ← alt
                    prev[v] ← u
    
    return dist[], prev[]

// Упрощенный псевдокод алгоритма Джонсона
function Johnson(Graph):
    // Добавляем вершину s и ребра с нулевым весом ко всем вершинам
    for each vertex v in Graph:
        add_edge(s, v, 0)
    
    // Ищем потенциалы с помощью Беллмана-Форда
    h = BellmanFord(Graph, s)
    if h содержит отрицательный цикл:
        return "Обнаружен отрицательный цикл"
    
    // Перевзвешиваем рёбра
    for each edge (u, v) with weight w in Graph:
        w' = w + h[u] - h[v]  // Новый вес гарантированно неотрицательный
    
    // Запускаем Дейкстру для каждой вершины
    for each vertex u in Graph:
        d = Dijkstra(Graph, u)  // Используем перевзвешенный граф
        // Восстанавливаем настоящие расстояния
        for each vertex v in Graph:
            d[v] = d[v] - h[u] + h[v]

// Матрица смежности: O(V²) память, O(1) доступ к весу ребра
vector<vector<int>> adj_matrix(V, vector<int>(V, INF));
 
// Список смежности: O(V+E) память, O(Degree(v)) для перебора соседей
vector<vector<pair<int, int>>> adj_list(V);  // (сосед, вес)

A --- 5 ---> B --- 2 ---> C
|            |            ^
|            |            |
3            8            1
|            |            |
v            v            |
D --- 4 ---> E --- 7 ---> F

#include <iostream>
#include <vector>
#include <limits>
 
const int INF = std::numeric_limits<int>::max();
 
std::vector<int> dijkstra(const std::vector<std::vector<int>>& graph, int source) {
    int n = graph.size();
    std::vector<int> dist(n, INF);
    std::vector<bool> visited(n, false);
    
    dist[source] = 0;
    
    for (int i = 0; i < n; i++) {
        // Находим вершину с минимальным расстоянием среди непосещённых
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        
        if (dist[u] == INF) break;  // Остальные вершины недоступны
        
        visited[u] = true;
        
        // Обновляем расстояния до соседей
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF) {
                int alt = dist[u] + graph[u][v];
                if (alt < dist[v]) {
                    dist[v] = alt;
                }
            }
        }
    }
    
    return dist;
}

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
 
typedef std::pair<int, int> Edge;  // (вес, вершина)
 
std::vector<int> dijkstra(const std::vector<std::vector<Edge>>& graph, int source) {
    int n = graph.size();
    std::vector<int> dist(n, std::numeric_limits<int>::max());
    dist[source] = 0;
 
    // Min-heap для эффективного извлечения минимума
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
    pq.push({0, source});
 
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
 
        // Пропускаем устаревшие записи
        if (d > dist[u]) continue;
 
        for (const auto& edge : graph[u]) {
            int v = edge.second;
            int weight = edge.first;
 
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
 
    return dist;
}

template<typename DistType, typename GraphType, typename GraphAdapter>
std::vector<DistType> dijkstra_generic(const GraphType& graph, 
                                      int source, 
                                      GraphAdapter adapter) {
    using std::vector;
    using std::priority_queue;
    using std::greater;
    using std::pair;
    
    const DistType INF = std::numeric_limits<DistType>::max();
    int n = adapter.vertexCount(graph);
    vector<DistType> dist(n, INF);
    
    using PQItem = pair<DistType, int>;
    priority_queue<PQItem, vector<PQItem>, greater<PQItem>> pq;
    
    dist[source] = 0;
    pq.push({0, source});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        adapter.forEachNeighbor(graph, u, [&](int v, DistType weight) {
            DistType alt = dist[u] + weight;
            if (alt < dist[v]) {
                dist[v] = alt;
                pq.push({dist[v], v});
            }
        });
    }
    
    return dist;
}

std::vector<int> parallel_dijkstra(const std::vector<std::vector<std::pair<int,int>>>& graph, 
                                 int source, int num_threads) {
    int n = graph.size();
    std::vector<int> dist(n, std::numeric_limits<int>::max());
    std::vector<std::atomic<bool>> relaxed(n);
    dist[source] = 0;
    
    auto processVertex = [&](int u) {
        relaxed[u] = true;
        for (const auto& [v, weight] : graph[u]) {
            int alt = dist[u] + weight;
            // Атомарно обновляем расстояние
            int expected = dist[v];
            while (alt < expected && !dist[v].compare_exchange_weak(expected, alt)) {
                alt = dist[u] + weight;  // Пересчитываем, т.к. dist[u] мог измениться
            }
            if (alt < expected) {
                relaxed[v] = false;  // Пометить для следующей итерации
            }
        }
    };
    
    // Инициализация потоков, разделение работы по фронтам волны и т.д.
    // ...
    
    return dist;
}

#include <ranges>
#include <concepts>
 
// Концепт для типа графа
template<typename G>
concept Graph = requires(G g, size_t u) {
    { g.size() } -> std::convertible_to<size_t>;
    { g[u] } -> std::ranges::range;
};
 
template<std::unsigned_integral DistType, Graph G>
std::vector<DistType> dijkstra_cpp20(const G& graph, size_t source) {
    using std::vector;
    using std::priority_queue;
    using std::greater;
    using std::pair;
    
    vector<DistType> dist(graph.size(), std::numeric_limits<DistType>::max());
    dist[source] = 0;
    
    priority_queue pq{greater{}, vector{pair{DistType{0}, source}}};
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (const auto& [v, weight] : graph[u]) {
            DistType alt = dist[u] + weight;
            if (alt < dist[v]) {
                dist[v] = alt;
                pq.emplace(alt, v);
            }
        }
    }
    
    return dist;
}

struct DijkstraResult {
    std::vector<int> distances;
    std::vector<int> predecessors;  // Предки для восстановления пути
};
 
DijkstraResult dijkstra_with_path(const std::vector<std::vector<Edge>>& graph, int source) {
    int n = graph.size();
    std::vector<int> dist(n, std::numeric_limits<int>::max());
    std::vector<int> pred(n, -1);  // -1 означает "нет предка"
    dist[source] = 0;
    
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
    pq.push({0, source});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (const auto& [weight, v] : graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pred[v] = u;  // Запоминаем, через какую вершину пришли
                pq.push({dist[v], v});
            }
        }
    }
    
    return {dist, pred};
}
 
// Восстановление пути от source до target
std::vector<int> reconstruct_path(const std::vector<int>& predecessors, int source, int target) {
    std::vector<int> path;
    for (int at = target; at != -1; at = predecessors[at]) {
        path.push_back(at);
        if (at == source) break;  // Достигли источника
    }
    std::reverse(path.begin(), path.end());  // Разворачиваем путь
    return path.empty() || path[0] != source ? std::vector<int>{} : path;  // Возвращаем пустой вектор, если пути нет
}

void generate_path_visualization(const std::vector<std::vector<Edge>>& graph, 
                             const std::vector<int>& path,
                             const std::string& filename) {
    std::ofstream dot_file(filename);
    dot_file << "digraph G {\n";
    
    // Добавляем все вершины
    for (int i = 0; i < graph.size(); ++i) {
        dot_file << "  " << i;
        if (std::find(path.begin(), path.end(), i) != path.end()) {
            dot_file << " [style=filled, fillcolor=lightblue]";  // Подсвечиваем вершины из пути
        }
        dot_file << ";\n";
    }
    
    // Добавляем все рёбра
    for (int u = 0; u < graph.size(); ++u) {
        for (const auto& [weight, v] : graph[u]) {
            dot_file << "  " << u << " -> " << v << " [label=\"" << weight << "\"";
            
            // Проверяем, является ли ребро частью пути
            bool is_edge_in_path = false;
            for (size_t i = 0; i < path.size() - 1; ++i) {
                if (path[i] == u && path[i+1] == v) {
                    is_edge_in_path = true;
                    break;
                }
            }
            
            if (is_edge_in_path) {
                dot_file << ", color=red, penwidth=2.0";  // Выделяем рёбра из пути
            }
            
            dot_file << "];\n";
        }
    }
    
    dot_file << "}\n";
}

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
 
// Определяем тип графа
typedef boost::adjacency_list<
    boost::listS,           // OutEdgeList: список для хранения исходящих рёбер
    boost::vecS,            // VertexList: вектор для хранения вершин
    boost::directedS,       // Направленный граф
    boost::no_property,     // Вершины без доп. свойств
    boost::property<boost::edge_weight_t, int>  // Рёбра с весами
> Graph;
 
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::property_map<Graph, boost::edge_weight_t>::type WeightMap;
 
std::vector<int> boost_dijkstra(const Graph& g, int source) {
    std::vector<Vertex> predecessors(boost::num_vertices(g));
    std::vector<int> distances(boost::num_vertices(g));
    
    // Получаем отображение весов
    WeightMap weight_map = boost::get(boost::edge_weight, g);
    
    // Запускаем алгоритм Дейкстры
    boost::dijkstra_shortest_paths(g, source,
        boost::predecessor_map(boost::make_iterator_property_map(
            predecessors.begin(), boost::get(boost::vertex_index, g)))
        .distance_map(boost::make_iterator_property_map(
            distances.begin(), boost::get(boost::vertex_index, g))));
    
    return distances;
}

// Дейкстра с ограничением на максимальное количество рёбер
std::vector<std::vector<int>> dijkstra_with_hop_limit(
    const std::vector<std::vector<Edge>>& graph, 
    int source, 
    int max_hops) {
    
    int n = graph.size();
    // dist[hop][node] = минимальное расстояние до node, используя ровно hop переходов
    std::vector<std::vector<int>> dist(max_hops + 1, 
                                   std::vector<int>(n, std::numeric_limits<int>::max()));
    dist[0][source] = 0;
    
    for (int hops = 0; hops < max_hops; ++hops) {
        for (int u = 0; u < n; ++u) {
            if (dist[hops][u] == std::numeric_limits<int>::max()) continue;
            
            for (const auto& [weight, v] : graph[u]) {
                int new_dist = dist[hops][u] + weight;
                if (new_dist < dist[hops+1][v]) {
                    dist[hops+1][v] = new_dist;
                }
            }
        }
    }
    
    return dist;
}

template<typename DistType>
std::vector<DistType> smart_dijkstra(const Graph& graph, int source) {
    // Анализируем свойства графа
    double density = graph.countEdges() / (double)(graph.countVertices() * (graph.countVertices() - 1));
    
    if (density > 0.5) {
        // Для плотных графов используем реализацию с массивом
        return dijkstra_array(graph, source);
    } else if (graph.countVertices() > 1000000) {
        // Для огромных графов используем распараллеленную версию
        return parallel_dijkstra(graph, source, std::thread::hardware_concurrency());
    } else {
        // В остальных случаях - стандартная реализация с кучей
        return dijkstra_heap(graph, source);
    }
}

// Сравнение асимптотик для разных реализаций:
// Массив: O(V^2) -> на графе 10,000 вершин ~= 100,000,000 операций
// Бинарная куча: O((V+E)log V) -> на разреженом графе с 10,000 вершин и 50,000 рёбер ~= 600,000 операций

// Простой встроенный профайлер для измерения времени выполнения
template<typename Func>
double measure_time(Func f) {
 auto start = std::chrono::high_resolution_clock::now();
 f();
 auto end = std::chrono::high_resolution_clock::now();
 return std::chrono::duration<double, std::milli>(end - start).count();
}
 
// Использование
double time_array = measure_time([&](){ dijkstra_array(graph, source); });
double time_heap = measure_time([&](){ dijkstra_heap(graph, source); });
std::cout << "Массив: " << time_array << " мс, Куча: " << time_heap << " мс\n";

// Оптимизация 1: Предварительная инициализация с резервированием памяти
std::vector<Edge> neighbors;
neighbors.reserve(expected_max_degree);  // Избегаем частых реаллокаций
 
// Оптимизация 2: Используем прямые индексы вместо дорогостоящего поиска по хэш-таблицам
std::vector<int> vertex_to_index(max_vertex_id + 1, -1);
for (int i = 0; i < vertices.size(); ++i) {
 vertex_to_index[vertices[i]] = i;
}
 
// Оптимизация 3: Кеширование часто используемых значений
const int weight_uv = graph.getWeight(u, v);  // Вычисляем один раз
if (dist[u] + weight_uv < dist[v]) { /* ... */ }

template<typename T, typename Priority>
class IndexedPriorityQueue {
private:
 std::vector<std::pair<T, Priority>> heap;
 std::unordered_map<T, size_t> index_map;  // Хранит индексы элементов в куче
 
 void sift_up(size_t i) { /* ... */ }
 void sift_down(size_t i) { /* ... */ }
 
public:
 void push(const T& item, Priority priority) {
     if (index_map.count(item)) {
         // Элемент уже в куче, обновляем приоритет если нужно
         size_t idx = index_map[item];
         if (priority < heap[idx].second) {
             heap[idx].second = priority;
             sift_up(idx);
         }
     } else {
         // Добавляем новый элемент
         index_map[item] = heap.size();
         heap.push_back({item, priority});
         sift_up(heap.size() - 1);
     }
 }
 
 // Другие методы: pop, top, empty...
};

// Упрощенная реализация A* (для сравнения с Дейкстрой)
std::vector<int> astar(const std::vector<std::vector<Edge>>& graph, 
                     int source, int target,
                     const std::vector<std::pair<double, double>>& coordinates) {
 // coordinates содержит геокоординаты (широта, долгота) для эвристики
 
 auto heuristic = [&](int v) -> double {
     // Евклидово расстояние в качестве эвристики
     double dx = coordinates[v].first - coordinates[target].first;
     double dy = coordinates[v].second - coordinates[target].second;
     return std::sqrt(dx*dx + dy*dy);
 };
 
 std::vector<int> dist(graph.size(), std::numeric_limits<int>::max());
 std::vector<int> pred(graph.size(), -1);
 dist[source] = 0;
 
 // Очередь с приоритетом f(n) = g(n) + h(n)
 // g(n) - известное расстояние от старта, h(n) - эвристическая оценка до цели
 using QItem = std::tuple<double, int, int>;  // (f, g, вершина)
 std::priority_queue<QItem, std::vector<QItem>, std::greater<QItem>> pq;
 pq.push({heuristic(source), 0, source});
 
 while (!pq.empty()) {
     auto [f, g, u] = pq.top();
     pq.pop();
     
     if (u == target) break;  // Достигли цели
     if (g > dist[u]) continue;  // Устаревшая запись
     
     for (const auto& [weight, v] : graph[u]) {
         int new_g = dist[u] + weight;
         if (new_g < dist[v]) {
             dist[v] = new_g;
             pred[v] = u;
             double new_f = new_g + heuristic(v);
             pq.push({new_f, new_g, v});
         }
     }
 }
 
 // Восстановление пути опущено для краткости
 return dist;
}

// Упрощённый пример иерархического подхода в навигационной системе
class HierarchicalRouter {
private:
    // Граф верхнего уровня - только основные магистрали
    Graph highway_network;
    // Детальные подграфы для каждого района
    std::vector<Graph> local_networks;
    // Соединительные точки между уровнями иерархии
    std::map<int, std::vector<PortalNode>> portals;
 
public:
    Path findRoute(int source, int target) {
        // 1. Находим ближайшие входы в магистральную сеть
        auto source_portals = findNearestPortals(source);
        auto target_portals = findNearestPortals(target);
        
        // 2. Прокладываем путь в верхнеуровневом графе между порталами
        Path highway_path = findHighwayPath(source_portals, target_portals);
        
        // 3. Соединяем локальными путями
        Path complete_path = connectWithLocalPaths(source, target, highway_path);
        
        return complete_path;
    }
};

// Динамические веса в навигационной системе
double calculateEdgeWeight(int roadSegmentId) {
    double baseTime = roadSegments[roadSegmentId].baseTransitTime;
    double currentTrafficFactor = getTrafficFactor(roadSegmentId);
    double weatherFactor = getWeatherImpact(roadSegmentId);
    double timeOfDayFactor = getTimeOfDayFactor(roadSegmentId);
    
    return baseTime * currentTrafficFactor * weatherFactor * timeOfDayFactor;
}

// Упрощенная структура для многокритериальной маршрутизации
struct NetworkLinkMetrics {
    double bandwidth;      // Пропускная способность (Mbps)
    double delay;          // Задержка (ms)
    double lossRate;       // Процент потерь пакетов
    double utilization;    // Текущая загрузка канала (%)
    double reliability;    // Надежность (0-1)
};
 
// Функция вычисления композитного веса для алгоритма Дейкстры
double calculateCompositeWeight(const NetworkLinkMetrics& metrics) {
    // Нормализованный вес, учитывающий все критерии с разными весовыми коэффициентами
    return 0.3 * (1.0 / metrics.bandwidth) +
           0.25 * metrics.delay +
           0.2 * metrics.lossRate +
           0.15 * metrics.utilization +
           0.1 * (1.0 - metrics.reliability);
}

// Интеграция с METIS для предварительной декомпозиции графа
void partition_and_process(const Graph& graph, int source) {
   // Разбиваем граф на подграфы примерно равного размера
   std::vector<int> partition = metis_partition(graph, NUM_PARTITIONS);
   
   // Строим графы верхнего уровня с метавершинами (подграфами)
   Graph meta_graph = build_meta_graph(graph, partition);
   
   // Сначала находим пути между метавершинами
   auto meta_paths = dijkstra(meta_graph, partition[source]);
   
   // Затем уточняем пути внутри подграфов
   // ...
}

// Использование "ориентиров" для ускорения поиска
std::vector<int> alt_dijkstra(const Graph& graph, int source, int target, 
                          const std::vector<int>& landmarks) {
   // Предварительно рассчитанные расстояния от/до ориентиров
   static std::vector<std::vector<int>> dist_to_landmarks;
   static std::vector<std::vector<int>> dist_from_landmarks;
   
   // Улучшенная эвристика, использующая неравенство треугольника
   auto improved_h = [&](int v) -> int {
       int max_h = 0;
       for (int lm : landmarks) {
           // Нижняя граница расстояния через ориентир
           max_h = std::max(max_h, 
               std::abs(dist_to_landmarks[lm][target] - dist_to_landmarks[lm][v]));
           max_h = std::max(max_h, 
               std::abs(dist_from_landmarks[lm][v] - dist_from_landmarks[lm][target]));
       }
       return max_h;
   };
   
   // Модифицированный A* с улучшенной эвристикой
   // ...
}

// "Ленивая" версия с прерыванием, когда достигает цели
auto lazy_dijkstra(const Graph& graph, int source, int target) {
   // Стандартный код инициализации...
   
   while (!pq.empty()) {
       auto [d, u] = pq.top();
       pq.pop();
       
       if (u == target) return d;  // Нашли цель, можно завершаться
       if (d > dist[u]) continue;
       
       // Релаксация рёбер...
   }
   
   return std::numeric_limits<int>::max();
}

// Граф с временными слоями
class TimeAwareGraph {
   std::vector<Graph> time_layers;  // Графы для разных временных срезов
   int time_resolution;  // Шаг дискретизации времени
   
public:
   // Находит кратчайший путь с учётом времени отправления
   Path findPathWithDeparture(int source, int target, time_t departure_time) {
       int start_layer = (departure_time / time_resolution) % time_layers.size();
       
       // Модифицированный Дейкстра, который может "перепрыгивать" между слоями
       // ...
   }
};