4488
правок
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача поиска кратчайших путей между всеми парами (APSP) заключается в нахождении кратчайших путей между всеми парами вершин в ориентированном графе с дугами неотрицательной действительной стоимости. Основное внимание уделяется кратчайшим расстояниям между вершинами, поскольку кратчайшие пути могут быть найдены с незначительным возрастанием стоимости. Классические алгоритмы решают задачу нахождения кратчайших путей между всеми парами вершин за кубическое время – O(n3). Наша задача заключается в достижении меньшего времени исполнения алгоритма для графа с небольшими целочисленными стоимостями дуг. | Задача поиска кратчайших путей между всеми парами (APSP) заключается в нахождении кратчайших путей между всеми парами вершин в ориентированном графе с дугами неотрицательной действительной стоимости. Основное внимание уделяется кратчайшим расстояниям между вершинами, поскольку кратчайшие пути могут быть найдены с незначительным возрастанием стоимости. Классические алгоритмы решают задачу нахождения кратчайших путей между всеми парами вершин за кубическое время – O(n3). Наша задача заключается в достижении меньшего времени исполнения алгоритма для графа с небольшими целочисленными стоимостями дуг. | ||
Пусть дан ориентированный граф G = (V, E), где V = {1, ..., n} – множество вершин, а E – множество дуг. Стоимость дуги (i, j) <math>\in</math> E обозначается как <math>d_{ | Пусть дан ориентированный граф G = (V, E), где V = {1, ..., n} – множество вершин, а E – множество дуг. Стоимость дуги (i, j) <math>\in</math> E обозначается как <math>d_{ij}</math>. Матрица D размера <math>n \times n</math> содержит элемент <math>d_{ij}</math> в позиции (i, j). Для простоты предположим, что <math>d_{ij}</math> > 0 и <math>d_{ii}</math> = 0 для всех i <math>\ne</math> j. Если не существует дуги из i в j, положим <math>d_{ij} = \infty</math>. Стоимость, или расстояние, пути представляет собой сумму стоимостей всех дуг на пути. Длина пути равна количеству дуг на пути. Кратчайшее расстояние между вершинами i и j равняется минимальной стоимости среди всех путей, ведущих от i до j, и обозначается как <math>d_{ij}^*</math>. Пусть <math>D^* = {d_{ij}^*}</math>. Значение n называется размером матрицы. | ||
Пусть A и B – матрицы (n, n). Умножение матриц A и B может производиться одним из трех способов: (1) Обычное матричное произведение над кольцом <math>C = AB</math>; (2) булево произведение матриц <math>C = A \cdot B</math>; (3) произведение матриц расстояния <math>С = A \times B</math>, где | Пусть A и B – матрицы (n, n). Умножение матриц A и B может производиться одним из трех способов: (1) Обычное матричное произведение над кольцом <math>C = AB</math>; (2) булево произведение матриц <math>C = A \cdot B</math>; (3) произведение матриц расстояния <math>С = A \times B</math>, где | ||
(1) | (1) <math>c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}</math> | ||
(2) | (2) |
правок