Кратко о самом алгоритме:
Алгоритм создан для нахождения кратчайшего пути в графе (в том числе в орграфе) от исходной вершины ко всем остальным. Алгоритм работает только на графах без отрицательного веса ребер, а также в графах, в которых отсутствует "закольцованность" вершины.
Когда я в интернете стал искать описание данного алгоритма, опять поразился. Практически везде был copy-past из книги какого-то автора (по-моему Вирт) на Pascal-е. Например на том же algolist. Данное описание не очень то внятное (ну по крайней мере мне оно таковым показалось). Куда лучше было описание алгоритма вWiki. Но там увы не было кода. Поэтому я решил отбросить все, и по описанию в вики написать самостоятельно. Собственно написанное я и хотел показать. Писал на сях...
Что нам нужно?
Чтобы выявить что нужно - разберем немного алгоритм.
Для начала все вершины графа нумеруются. Всем ребрам графа должны быть розданы их веса. Эти два параметра описывают сам граф. Описать его можно двумя способами - с помощь матрицы смежности X(i,j), где индексы i и j являются номерами вершин, а значение X(i,j) - вес дуги (ребра) между этими вершинами. Если из вершины i в вершину x нет пути, то вес равняется нулю (на самом деле это может быть не так).
Итак, как задавать граф мы разобрались (можно задавать и другим способом, более экономя память, но это будет немного позже).
Алгоритм работает так. Каждая вершина помечается каким-то число (как правило большим, больше суммы всех весов графа). Например число может равняться INT_MAX. Исходная вершина помечается нулем - это означает что путь от нее самой к себе составляет равняется нулю.
Далее перебираются все смежные вершины текущей (в данном случае исходной). Метка каждой смежной вершины заменяется на [вес ребра от текущей вершины (в данном случае исходной) до очередной смежной вершины] + [метка текущей вершины (в данном случае исходной)]. Данная замена происходит только в том случае, если метка очередной смежной вершины меньше данной суммы. Так как сейчас все вершины помечены большим числом, то замена произойдет по всем смежным вершинам, и на первом шаге будет равняться весу ребра между источником и смежной вершиной (так как метка источника равна 0).
После того как все смежные вершины перебраны, нужно выбрать очередную опорную вершину вместо исходной. Выбирается ближайшая вершина к текущей (в данном случае исходной). Текущая же опорная вершина больше не учитывается, и путь к ней больше не считается не из какой вершины.И опять от выбранной вершины проверяются все смежные, заменяя метки. Важно понимать что замена будет производиться только тогда, когда сумма веса ребра и метки текущей вершины меньше метки целевой вершины. Иначе метка целевой вершины сохраняется.
На каждой итерации очередная опорная вершина добавляется к списку "перебранных". Алгоритм завершается как только все вершины будут перебраны. После полного прохода каждая вершина будет иметь метку, равную минимальному расстоянию от исходной вершины до каждой помеченной.
Итак. Что же нужно.
1. Матрица смежности всех вершин, которая описывает граф.
2. Массив текущих меток вершин. Вообще во многих источника говорится что это должен быть двумерный массив. Одна строка будет описывать одну итерацию. Я же взял одномерный массив. Так будет в общем-то проще, да и память сохранится.
3. Данный одномерный массив будет хранить индекс, на котором метка вершины изменилась на меньшую. Так можно будет отследить путь от исходной вершины до любой другой, пройдя все вершины по массиву п. 4
4. Массив выведенных из расчета вершин. Здесь будут храниться все вершины, выведенные из расчета именно в том порядке, в котором они выбывали. Это важно для дальнейшего нахождения всех ребер путей для конкретной вершины по массиву п. 3
5. Массив, хранящий пометки о том, что вершина выведена из расчета. Индекс массива - номер вершины. 0 - вершина не выведена, 1 - вершина выведена
Дополнительно понадобятся переменные для работы с индексами массивов, а именно
1. Номер текущей опорной вершины
2. Индекс для массива, хранящего выведенные вершины (п. 4)
Ну и наконец нам понадобится функция, вычисляющая ближайшую вершину к нужной.
Итак, приступим. Сначала реализуем функцию выбора минимальной (ближайшей) вершины к выбранной.
- Код: Выделить всё
int min_all_indx(int* piArray, int iCountElements, int* piChecksTops)
{
int iCurMin = INT_MAX;
int iCurIndex = INT_MAX;
for(int i = 0; i < iCountElements; i++)
{
if (piArray[i]!=INT_MAX && piChecksTops[i]!=1)
{
if (piArray[i] < iCurMin)
{
iCurMin = piArray[i];
iCurIndex = i;
}
}
}
return iCurIndex;
}
Функция возвращает индекс в одномерном массиве с минимальной меткой.
Параметры
1. int* piArray - указатель на массив. В него будем передавать массив с текущими метками всех вершин. Понятно что выбирать минимальный элемент для первой итерации не нужно.
2. int iCountElements - количество элементов в массиве.
3. int* piChecksTops - указатель на массив, хранящий пометки о том, что вершина проверена (0 или 1)
Функция проверяет все не исключенные вершины и выбирает вершину с минимальной меткой. Ничего сложного вообще.
Далее сам алгоритм. Начнем с инициализации.
Для удобства задания матрицы смежности я использовал такое описание
- Код: Выделить всё
int matrix[6][6] = {0, 6, 1, 0, 0, 0,
0, 0, 4, 0, 3, 0,
0, 0, 0, 0, 6, 4,
5, 0, 3, 0, 0, 0,
0, 0, 0, 0, 0, 6,
0, 0, 0, 3, 0, 0 };
Далее я эту структуру перевожу в динамический массив для программного удобства. Но можно работать и так.
- Код: Выделить всё
int ** matrix_ex = (int**) calloc(6, sizeof(int*));
for (int i=0; i<6; i++)
matrix_ex[i] = (int*) calloc(6, sizeof(int));
for (int i=0; i<6; i++)
for(int j=0; j<6; j++)
matrix_ex[i][j] = matrix[i][j];
Далее
Массив весов всех вершин. Сколько вершин - столько и элементов.
- Код: Выделить всё
int* piWeights = (int*) calloc(6, sizeof(int));
Помечаем каждую вершину большим числом - ни у одной вершины не известен кротчайший путь.
- Код: Выделить всё
for (int i=0; i<6; i++)
piWeights[i] = INT_MAX;
Массив исключенных вершин. Здесь будут храниться именно номера вершин. Я взял как исходную вершину №1, поэтому на первом месте в массиве указано 1.
- Код: Выделить всё
int i_tops[6] = {1, 0, 0, 0, 0, 0};
Массив пометок пройденных вершин. Первую вершину мы берем как исходную, поэтому она уже помечена.
- Код: Выделить всё
int i_checks[6] = {1, 0, 0, 0, 0, 0};
Массив...который хранит номер итерации, на котрой метка вершины изменилась
- Код: Выделить всё
int i_finds[6] = {0, 0, 0, 0, 0, 0};
Помечаем вес первой вершины нулем 0 - это путь к самой себе.
- Код: Выделить всё
piWeights[0] = 0;
Номер текущей вершины и текущий индекс вершины в массиве i_tops равны нулю. Первая переменная хранит номер вершины, вторая индекс в массиве. Все вроде ясно.
- Код: Выделить всё
int iCurTopIndex = 0;
int iCur_tps_index = 0;
Итак. Инициализация есть. Теперь начинаем итерации. Итераций будет пять, так как одну вершину мы уже взяли. Код с комментариями приведен ниже
- Код: Выделить всё
while (iCur_tps_index!=5) // пока индекс в массиве вершин не равен 5 - концу массива :)
{
for (int i = 0; i < 6; i++) // перебераем каждую вершину
{
if (i_checks[i]!=1) // если i-я вершина еще не проверена
{
if (matrix_ex[iCurTopIndex][i]!=0) // и если i-я вершина смежная
{
// проверяем, меньше ли сумма метки текушей опорной вершины iCurTopIndex и веса ребра от этой вершины до i-й,
// и если да, то заменяем вес этой вершины на эту сумма
// здесь же в массив i_finds заносим индекс iCur_tps_index - на каком шаге изменилась метка (стала меньше)
if (piWeights[i] > (piWeights[iCurTopIndex] + matrix_ex[iCurTopIndex][i]))
{
piWeights[i] = piWeights[iCurTopIndex] + matrix_ex[iCurTopIndex][i];
i_finds[i] = iCur_tps_index;
}
}
}
}
iCurTopIndex = min_all_indx(piWeights, 6, i_checks); // опять выбираем опорную вершину с наименьшей меткой
i_checks[iCurTopIndex] = 1; // в массиве меток ставим этой вершине метку "проверена"
iCur_tps_index++; // индекс для записи очередной опорной вершины пиращаем
i_tops[iCur_tps_index] = iCurTopIndex; // и записываем по этому индексу номер вершины, которая выбирается как опорная
}
Как только пройдемся по всем вершинам, попробуем найти путь, ну например к вершине 4
- Код: Выделить всё
for (int i = 1; i < i_finds[3]+1; i++)
std::cout<<i_tops[i]<<" ";
std::cout<<"===="<<piWeights[3];
Путь будет лежать через вершину 3, 6 и его длинна будет равнять 8. (переведите индексы вершин в нормальное представление, выводится конечно же вершины 2 и 5)
Ну и напоследок сам граф, для проверки.
Замечания, предложения, вопросы. Все принимается.
Продолжение этой темы будет далее. И изучение графов также.
З.Ы. ох тяжко же столько писать...