GraphProcessorFrontend/src/views/AboutPageView.vue - master - vibecoder123/GraphProcessorFork

GraphProcessorFrontend/src/views/AboutPageView.vue
33 строки3 KB
coder6497
Added bordered table for distance processing results
24 мар 2026, 17:04
24 мар 2026, 17:0479dc19d
<template>
    <h3>This is graph processor</h3>
    <textarea class="textarea">
        Основная идея: Нахождение кратчайших путей от одной стартовой вершины до всех остальных в взвешенном графе с неотрицательными весами рёбер.
        Как работает (жадный алгоритм):
        Присвоить начальной вершине расстояние 0, а всем остальным — бесконечность.
        Поместить все вершины в приоритетную очередь (Min-Heap) по текущему расстоянию.
        Пока очередь не пуста:
        Извлечь вершину u с минимальным текущим расстоянием.
        Для каждого соседа v вершины u:
        Вычислить новое расстояние: расстояние_до_u + вес_ребра(u, v).
        Если это расстояние меньше текущего известного расстояния до v, то обновить расстояние до v и запомнить u как предшественника v (для восстановления пути).
        Повторять, пока не будут обработаны все вершины.
        Ключевые свойства:
        Работает только с неотрицательными весами рёбер. Отрицательные веса нарушают его логику.
        Гарантированно находит оптимальные кратчайшие пути.
        Сложность зависит от реализации структуры данных:
        С массивом: O(V² + E) — хорошо для плотных графов.
        С бинарной кучей (приоритетной очередью): O((V + E) log V) — лучше для разреженных графов.
        С более продвинутыми кучами (Фибоначчи) можно улучшить до O(E + V log V).
        Где применяется:
        Маршрутизация в сетях (протоколы типа OSPF, IS-IS).
        Построение карт и навигация (поиск кратчайшего пути по времени или расстоянию).
        Моделирование потоков.
        Как основа для более сложных алгоритмов (например, A* с эвристикой).
    </textarea>
</template>

<script setup lang="ts">

</script>

<style scoped></style>