Самым простым вариантом будет использование алгоритма Флойда-Уоршалла для поиска расстояний от каждой до каждой вершины. Асимптотическая сложность 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;
