Поиск всех кратчайших путей в графе. На вход подается матрица смежности графа (поле last структуры), где на месте отсутствия связей должен быть INT_MAX, а по диагонали нули. Метод преобразует так матрицу, что наименьший путь с вершины i в вершину j будет равен M[i][j].last
Пример:
for (i = 0; i < size; i++) {
for (j = 0; j < size; j++) {
fscanf(file, "%d", &M[i][j].last);// чтение веса дуги (i,j) из файла
if (M[i][j].last == -1) M[i][j].last = INT_MAX;// если в файле -1, то нет такой дуги
if (i == j) M[i][j].last = 0;// диагональные элементы =0
}
}
findPathsShimbel(M, size);// считаем

Кусок из моей лабы по C++. Может кому-то пригодится

                        
typedef struct {

    int n, last;

} Cell;

 

void findPathsShimbel(Cell **M, int n) {

    int run = 1, min, i, j, k, sum;

    while (run) {

        run = 0;

        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {

                min = INT_MAX;

                for (k = 0; k < n; k++) {

                    if (M[i][k].last == INT_MAX || M[k][j].last == INT_MAX)

                        sum = INT_MAX;

                    else sum = M[i][k].last + M[k][j].last;

                    min = min > sum ? sum : min;

                }

                if (min < M[i][j].last) {

                    run = 1;

                    M[i][j].n = min;

                } else M[i][j].n = M[i][j].last;

            }

        }

        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {

                M[i][j].last = M[i][j].n;

            }

        }

    }

}