вот собственно код.может кто-то свежим взглядом заметит ошибку)).комменты остались с поиска кратчайших путей
#include <stdio.h>
//#include <iostream.h>
#include <conio.h>
#define VERTEXES 6 //Число вершин в графе
int v;
int main(int argc, char* argv[])
{
// clrscr();
int infinity=1000;
int p= VERTEXES;
int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,
1,0,5,0,0,1,
0,5,0,5,20,1,
0,0,5,0,3,2,
1,0,20,3,0,10,
3,1,1,2,10,0 };
// Будем искать путь из вершины s в вершину g
int s; // Номер исходной вершины
int g; // Номер конечной вершины
printf("Enter s: "); // Номер может изменяться от 0 до p-1
scanf("%i",&s);
printf("Enter g: ");
scanf("%i",&g);
int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
// x=0 - еще не найден кратчайший путь в i-ю вершину,
// x=1 - кратчайший путь в i-ю вершину уже найден
int t[VERTEXES]; //t - длина кратчайшего пути от вершины s в i
int h[VERTEXES]; //h - вершина, предшествующая i-й вершине
// на кратчайшем пути
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<p;u++)
{
t=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x=0; // и нет кратчайшего пути ни для одной вершины
}
h=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t=0; // Кратчайший путь из s в s равен 0
x=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<p;u++)
{
if(a[v]==0)continue; // Вершины u и v несмежные
if(x==0 && t<t[v]+a[v]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t=t[v]+a[v]; //запоминаем более короткую длину пути в
//массив t и
h=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
}
// Ищем из всех длин некратчайших путей самый короткий
int w=-infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<p;u++) // Перебираем все вершины.
{
if(x==0 && t>w) // Если для вершины не найден кратчайший
// путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t;
}
}
if(v==-1)
{
printf("No way from %s to %g.",s,g);
break;
}
if(v==g) // Найден кратчайший путь,
{ // выводим его
printf("Min way from %i to %i.",s,g);
u=g;
while(u!=s)
{
printf(" %i",u);
u=h;
}
printf(" %i Way's length - %i",s,t[g]);
break;
}
x[v]=1;
}
getch();
}
