Алгоритм Флойда Warshall с максимальной шаги позволили

Можно ли модифицировать алгоритм Флойда-Уорсхолла при решении задачи о кратчайшем пути для ориентированного взвешенного графа сn вершинами таким образом, чтобы каждый кратчайший путь имел не болееm шагов? Точнее, для каждой пары узлов i и j вы найдете кратчайший направленный путь от i до j, содержащий не более m узлов. Остается ли временная сложность по-прежнему O(n3)?

3 3
algorithm dynamic-programming shortest-path

3 ответа:

Тем временем я нашел O(н3log m ) алгоритм поиска всех пар кратчайших путей (ASP) для графа с n узлами, такими что ни один путь не содержит более m узлов.

Даны две n x n матрицы, скажем A = [аij] и B = [bij], их произведение расстояний равно n x n Матрица C = [cij] = A x B , определяемый c ij = мин1≤к≤n {аИК + bкДж}.

Это связано с ASP следующим образом. Дана взвешенная матрицаE расстояний в графе, En является матрицей всех пар кратчайшего пути. Если мы добавим ограничение, что ни один путь не содержит более m узлов, то матрица Eм это решение для ASP. Поскольку вычислительная мощность может быть найдена в O (log m ) времени, это дает нам O(n3log M ) алгоритм.

Здесь можно найти более быстрые алгоритмы вычисления произведения расстояний матриц в некоторых частных случаях, но тривиальный O(n3) для меня этого достаточно, поскольку общее время идет почти так же быстро, как Флойд-Уорсхолл.

2

Да и да.

  • каждая итерация algotithm добавляет одну единицу длины путей, которые вы ищете. Таким образом, если вы ограничите итерации до m, то вы найдете путь длиной не более m.
  • сложность останется O(n^3) в худшем случае m -> n. однако более точной оценкой будет O (m * n^2).
0

Я полагаю, что это можно сделать с другой структурой данных (которая позволит вам отслеживать количество шагов)?

Поскольку обычно Флойд-Уорсхолл работает с матрицей связности (где матрица [j] [k] представляет расстояние между узлами j и k), вместо того, чтобы сделать эту матрицу целым числом, мы можем сделать ее структурой, которая имеет два целых числа : расстояние между двумя узлами и число шагов между ними.

Я написал кое-что на C++, чтобы объяснить, что я имею в виду: 

#define INFINITY 9999999

struct floydEdge
{
    int weight;
    int steps;
};

floydEdge matrix[10][10];

int main()
{
    //We initialize the matrix
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            matrix[j][k].weight=INFINITY;
            matrix[j][k].steps=0;
        }
    }

    //We input some weights
    for(int j=0;j<10;j++)
    {
        int a, b;
        cin>>a>>b;
        cin>>matrix[a][b].weight;
        matrix[b][a].weight=matrix[a][b].weight;
        matrix[a][b].steps=matrix[b][a].steps=1;
    }

    //We do the Floyd-Warshall, also checking for the step count as well as the weights
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            for(int i=0;i<10;i++)
            {
                //We check if there is a shorter path between nodes j and k, using the node i. We also check if that path is shorter or equal to 4 steps.
                if((matrix[j][k].weight > matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<=4))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
                //If the path is not shorter, we can also check if the path is equal BUT requires less steps than the path we currently have.
                else if((matrix[j][k].weight == matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<matrix[j][k].steps))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
            }
        }
    }
    return 0;
}

Я считаю (но я не совсем уверен), что это работает идеально (всегда давая кратчайший путь между всеми узлами). Дайте ему попробовать и дайте мне знать!

0