Поиск кратчайшего пути на графе

#include <iostream>
 
using namespace std;
 
int i, j, n, num, start_pos, end_pos;
 
int infinity = 99999;
 
int visit[15];
 
int matrix[15][15];
 
int lenght[15];
 
char s[100];
 
char path[100][15];
 
void _tmain()
 
{
 
setlocale(LC_ALL, "Russian");
 
cout << "Введите количество вершин: ";
 
cin >> n;
 
cout << "\n";
 
for (i = 0; i<n; i++)
 
for (j = 0; j<n; j++) matrix[i][j] = 0;
 
for (i = 0; i<n; i++)
 
for (j = i + 1; j<n; j++)
 
{
 
cout << "Расстояние от " << i + 1 << " до " << j + 1 << ": ";
 
cin >> matrix[i][j];
 
}
 
cout << "\n\n ";
 
for (i = 0; i<n; i++) cout << " X" << i + 1;
 
cout << endl << endl;
 
cout << "\n";
 
for (i = 0; i<n; i++)
 
{
 
printf("X%d", i + 1);
 
for (j = 0; j<n; j++)
 
{
 
printf("%6d", matrix[i][j]);
 
matrix[j][i] = matrix[i][j];
 
}
 
printf("\n\n");
 
}
 
for (i = 0; i<n; i++)
 
for (j = 0; j<n; j++)
 
if (matrix[i][j] == 0) matrix[i][j] = infinity;
 
cout << "\n";
 
for (;
 
{
 
cout << "Введите начальную вершину: ";
 
cin >> start_pos;
 
if (start_pos<1 || start_pos>n)
 
{
 
cin.clear();
 
fflush(stdin);
 
cout << "Некорректный ввод. Введите номер вершины в интервале от 1 до " << n << "\n";
 
}
 
else break;
 
}
 
start_pos--;
 
for (;
 
{
 
cout << "Введите конечную вершину: ";
 
cin >> end_pos;
 
if (end_pos<1 || end_pos>n)
 
{
 
cin.clear();
 
fflush(stdin);
 
cout << "Некорректный ввод. Введите номер вершины в интервале от 1 до " << n << "\n";
 
}
 
else break;
 
}
 
end_pos--;
 
cout << "\n";
 
if (start_pos == end_pos)
 
{
 
cout << "Начальная и конечная точка совпадают\n" << endl;
 
return;
 
}
 
for (i = 0; i<n; i++)
 
{
 
visit[i] = 0;
 
lenght[i] = infinity;
 
}
 
lenght[start_pos] = 0;
 
visit[start_pos] = 1;
 
num = start_pos;
 
itoa(start_pos + 1, s, 10);
 
for (i = 1; i <= n; i++)
 
{
 
strcpy(path[i], "X");
 
strcat(path[i], s);
 
}
 
do
 
{
 
for (i = 0; i<n; i++)
 
if ((matrix[num][i] != infinity) && (!visit[i]) && (i != num))
 
{
 
if (lenght[i]>lenght[num] + matrix[num][i])
 
{
 
itoa(i + 1, s, 10);
 
strcpy(path[i + 1], path[num + 1]);
 
strcat(path[i + 1], "-X");
 
strcat(path[i + 1], s);
 
}
 
if (lenght[i]>lenght[num] + matrix[num][i]) {
 
lenght[i] = lenght[num] + matrix[num][i];
 
}
 
}
 
for (i = 0; i<n; i++)
 
if (!(visit[i])) num = i;
 
for (i = 0; i<n; i++)
 
if ((lenght[num]>lenght[i]) && (!visit[i])) num = i;
 
visit[num] = 1;
 
}
 
while (num != end_pos);
 
if (lenght[num] != infinity)
 
{
 
cout << "Путь: " << path[num + 1] << endl;
 
cout << "Длина пути: " << lenght[num] << endl << endl;
 
}
 
else
 
cout << "Такого пути не существует" << endl << endl;
 
}