Задать вопрос
Flaker

Flaker

Ответы пользователя по тегу Алгоритмы

  • Алгоритм Флойда-Уоршелла

    Flaker
    @Flaker
    Похоже реализация не совсем верная.

    Такая проверка не имеет смысла.
    if ((dist[i, k] * dist[k, j] != 0) && (i != j))

    Взгляни на e-maxx. Там подробное описание.

    Я реализовывал это на C++ таким образом:
    #include <iostream>

#define INF 9000000
#define MatrixLen 5

/* Алгоритм Флойда — Уоршелла.*/

/* Исходная матрица расстояний */
int matrix[MatrixLen][MatrixLen] =
{
    {0, 5, 2, INF, INF},
    {5, 0, INF, 7, INF},
    {2, INF, 0, 2, 8},
    {INF, 7, 2, 0, 1},
    {INF, INF, 8, 1, 0}
};

    /* Поиск расстояния минимального пути от каждой до каждой вершины */
    for (size_t k(0); k < MatrixLen; ++k)
        for (size_t i(0); i < MatrixLen; ++i)
            for (size_t j(0); j < MatrixLen; ++j)
                if (matrix[i][k] < INF && matrix[k][j] < INF)
                    if (matrix[i][k] + matrix[k][j] < matrix[i][j])
                        matrix[i][j] = matrix[i][k] + matrix[k][j];


    int from = 0;
    int to = 4;

        /* Теперь минимальное расстояние от любой до любой будет matrix[ОТКУДА][КУДА] */

    std::cout << "Path length from " << from << " to " << to << " is " << matrix[from][to] << std::endl;


    Тут существуют вершины, между которыми нет пути. Расстояние между ними при этом задается как INF.
    Ответ написан
    6 комментариев
    6 комментариев

  • Задача расчета расстояния путей между городами с использование графов в C++?

    Flaker
    @Flaker
    Самым простым вариантом будет использование алгоритма Флойда-Уоршалла для поиска расстояний от каждой до каждой вершины. Асимптотическая сложность n^3, поэтому, использовать в реальных проектах не стоит, зато реализация самого алгоритма элементарная (по сути, полный перебор).

    #include <iostream>

#define INF 9000000
#define MatrixLen 5

/* Алгоритм Флойда — Уоршелла.*/

/* Исходная матрица расстояний */
int matrix[MatrixLen][MatrixLen] =
{
	{0, 5, 2, INF, INF},
	{5, 0, INF, 7, INF},
	{2, INF, 0, 2, 8},
	{INF, 7, 2, 0, 1},
	{INF, INF, 8, 1, 0}
};

	/* Поиск расстояния минимального пути от каждой до каждой вершины */
	for (size_t k(0); k < MatrixLen; ++k)
		for (size_t i(0); i < MatrixLen; ++i)
			for (size_t j(0); j < MatrixLen; ++j)
				if (matrix[i][k] < INF && matrix[k][j] < INF)
					if (matrix[i][k] + matrix[k][j] < matrix[i][j])
					{
						matrix[i][j] = matrix[i][k] + matrix[k][j];
						parents[i][j] = k;
					}


	int from = 0;
	int to = 4;

        /* Теперь минимальное расстояние от любой до любой будет matrix[ОТКУДА][КУДА] */

	std::cout << "Path length from " << from << " to " << to << " is " << matrix[from][to] << std::endl;
    Ответ написан
    Комментировать
    Комментировать