Всем спасибо за советы.
Да, извиняюсь, забыл уточнить, что в графе нет циклов, каждую вершину можно посещать только один раз.
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define TOPS 4
int v;
int main(int argc, char* argv[])
{
int infinity=10000;
int p = TOPS;
int** a = LoadDataFromFile("data1.txt");
int s = 1;
int g = 3;
int x[TOPS]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
int t[TOPS]; //t[i] - длина кратчайшего пути от вершины s в i
int h[TOPS]; //h[i] - вершина, предшествующая i-й вершине
// на кратчайшем пути
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<p;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<p;u++)
{
if(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в
//массив t и
h[u]=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
printf("%d\n",t[u]);
}
// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<p;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины u не найден кратчайший
// путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}
if(v==-1)
{
printf("No ways");
break;
}
if(v==g) // Найден кратчайший путь,
{ // выводим его
printf("Min way = ");
u=g;
while(u!=s)
{
printf("%d<-",u);
u=h[u];
}
printf("%d\n",s);
printf("%d",t[g]);
break;
}
x[v]=1;
}
free(a);
return 0;
}
Здесь из файла считывается матрица смежности.
Нужно применить Дейкстру для каждой вершины, взять максимальную из длин найденнных кратчайших путей.
Что-то с ходу не соображу, как тут это сделать, навскидку мысль поменять вот тут:
, но это, вроде, не совсем правильно работает...
(где V и E - кол-во вершин и рёбер соответственно), а в случае матрицы - 
(где n - кол-во вершин) ?
, но применительно к данной задаче... ?