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;