JOHNSON ALGORITMI
Keywords:
Kalit so'zlar: Johnson algoritmi, eng qisqa yo'l, barcha juftlik, graf nazariyasi, Dijkstra algoritmi, Bellman-Ford algoritmi, manfiy qirralar, siyrak graf, algoritmik murakkablik, optimizatsiya, yo'l topish, graf algoritmlari, dasturlash, ma'lumotlar strukturasi, Keywords: Johnson algorithm, shortest path, all-pairs, graph theory, Dijkstra algorithm, Bellman-Ford algorithm, negative edges, sparse graph, algorithmic complexity, optimization, pathfinding, graph algorithms, programming, data structures, Ключевые слова: алгоритм Джонсона, кратчайший путь, все пары, теория графов, алгоритм Дейкстры, алгоритм Беллмана-Форда, отрицательные рёбра, разреженный граф, алгоритмическая сложность, оптимизация, поиск пути, алгоритмы на графах, программирование, структуры данныхAbstract
Johnson algoritmi barcha juftlik eng qisqa yo'llar (All-Pairs Shortest Path) masalasini hal qilish uchun mo'ljallangan samarali algoritm hisoblanadi. U 1977-yilda Donald B. Johnson tomonidan ishlab chiqilgan bo'lib, siyrak (sparse) graflarda Dijkstra va Bellman-Ford algoritmlarining kombinatsiyasini ishlatadi. Johnson algoritmi manfiy qirrali graflar bilan ishlash imkoniyatiga ega bo'lib, Floyd-Warshall algoritmiga nisbatan ko'plab hollarda yuqori samaradorlik ko'rsatadi. Algoritm avval Bellman-Ford yordamida manfiy tsikllarni aniqlaydi va qirra og'irliklarini qayta o'zgartiradi, so'ngra har bir tugun uchun Dijkstra algoritmini qo'llaydi. Ushbu maqolada Johnson algoritmining ishlash prinsipi, asosiy bosqichlari, murakkablik tahlili va boshqa algoritmlarga nisbatan afzalliklari ko'rib chiqiladi.
Johnson's algorithm is an efficient algorithm designed to solve the All-Pairs Shortest Path problem. Developed by Donald B. Johnson in 1977, it uses a combination of Dijkstra's and Bellman-Ford algorithms on sparse graphs. Johnson's algorithm can handle graphs with negative edge weights and often shows superior performance compared to the Floyd-Warshall algorithm. The algorithm first uses Bellman-Ford to detect negative cycles and reweight edges, then applies Dijkstra's algorithm for each vertex. This paper examines the working principle of Johnson's algorithm, its main stages, complexity analysis, and advantages over other algorithms.
Алгоритм Джонсона является эффективным алгоритмом для решения задачи поиска кратчайших путей между всеми парами вершин (All-Pairs Shortest Path). Разработанный Дональдом Б. Джонсоном в 1977 году, он использует комбинацию алгоритмов Дейкстры и Беллмана-Форда для работы с разреженными графами. Алгоритм Джонсона может работать с графами, содержащими рёбра с отрицательными весами, и часто показывает превосходную производительность по сравнению с алгоритмом Флойда-Уоршелла. В данной статье рассматриваются принципы работы алгоритма Джонсона, его основные этапы, анализ сложности и преимущества перед другими алгоритмами.
