Есть взвешенный граф и дан список смежности весов в файле.
- 2;11
- 3;1 4;6 1;11
- 2;1 4;2
- 3;2 2;6
Где 2;11 - означает, что 1 вершина соединена со 2 вершиной ребром весом 11. 3;1 - означает, что 2 вершина соединена с 3 вершиной ребром весом 1 и т.д. Структура хранения этого списка - односвязные списки.
struct data{
int node;
int weight;
};
//...........
data x{};
List<data> *a;
a = new List<data> [n];
cout << "Чтение матрицы весов ребер:\n";
for (int j = 0; j < n; ++j) {
for (int i = 0; i < countInRow[j]; i++) {
fscanf(f1, "%d;%d", &x.node,&x.weight);
a[j].push_back(x);
}
}
cout << "Матрица кратчайших путей:" << endl;
Dijkstra(a,n,0);
Нужно найти матрицу кратчайших путей. Пробовал алгоритмы Флойда — Уоршелла и Дейкстры, но ничего не получилось. Везде они даны для матрицы весов. Пробовал переделать их под свою структуру хранения, начались ошибки с памятью.
upd: Сделал функцию, которая возращает вес ребра и переделал алгоритм Флойда - Уоршелла под списки. Теперь я можно сказать восстановил матрицу весов, но кратчайшие пути не считает.
int foo(List<data> *a,int row,int col){
if (row == col) return 0;
int size = a[row-1].GetSize();
for (int i=0;i<size;i++) {
if (a[row - 1][i].node == col) {
return a[row - 1][i].weight;
}
}
return 10000;
}
void Floyd_Warshall(List<data> *a, int numberOfVert) {
int **matrix=new int*[numberOfVert];
for (int i=0;i<numberOfVert;i++)
matrix[i] = new int [numberOfVert]{};
for (int k = 0; k < numberOfVert; k++) { //Пробегаемся по всем вершинам и ищем более короткий путь через вершину k
for (int i = 0; i < numberOfVert; i++) {
for (int j = 0; j < numberOfVert; j++) {
if (i!=j) {
matrix[i][j] = std::min(foo(a,i+1,j+1), foo(a,i+1,k+1) +
foo(a,k+1,j+1));
} //Новое значение ребра равно минимальному между старым ребром и суммой ребер
}
}
}
//Печать матрицы кратчайших путей
for (int i = 0; i < numberOfVert; ++i) {
for (int j = 0; j < numberOfVert; ++j) {
cout << matrix[i][j] << "\t";
}
cout << endl;
}
}