Не могу вывести кротчайший путь

[Владислав11]

Вот пишу курсовую , и преподша сказала, чтобы програмка выводила все возможные кротчайшие пути, а не один.Как это сделать ???
вот исходник :

#include <iostream.h>
#include <stdlib.h>
const int INFINITY=100000000;
const int MAXN=100;
bool check (char[]); 
int main()
{
	int i,j,v,u,n,m,c,min,s,t,e[MAXN][MAXN]={0},w[MAXN][MAXN]={0};
	int ne[MAXN]={0},use[MAXN]={0},p[MAXN]={0},d[MAXN]={0};
	char temp[]="";
	bool ok=false;
// n - kol-vo versyn grafa
// m - kol-vo reber
// t,s - vershuny puti
// u,v - svazannie vershuny
// c - ves rebra 
// d -massiv dliny putey v kazhduyu versuny
// w - matrica smezhnosti
// p - massiv predkov (dla vosstanovleniya puti)
// e - matrica - nabor massivov svyiazi reber
// use - massiv proidenyh vershyn na tekushem etape
// ne - kolichestvo reber, sviazannyh s vershynoy V
// min - minim dlina puti na shage 


while (ok==false)
{
 cout<<"Wwedit kol-vo vershin grafa:";
 cin>> temp;
 ok=check(temp);
 if (ok==false) cout<<"Wwod newernuy.\n";
 else n=atoi(temp);}
ok=false;
while (ok==false)
{
 cout<<"Wwedit kol-vo reber grafa:";
 cin>> temp;
 ok=check(temp);
 if (ok==false) cout<<"Wwod newernuy.\n";
 else m=atoi(temp);}
ok=false;
while (ok==false)
{
 cout<<"Wwedit nashalnuju vershinu grafa:";
 cin>> temp;
 ok=check(temp);
 if (ok==false) cout<<"Wwod newernuy.\n";
 else t=atoi(temp);}
ok=false;
while (ok==false)
{
 cout<<"Wwedit konechnuju vershinu grafa:";
 cin>> temp;
 ok=check(temp);
 if (ok==false) cout<<"Wwod newernuy.\n";
 else s=atoi(temp);}
 
 for (i=1;i<=m;i++) 
	{   
	  cout<<"Wwedit pervuju vershinu,vtoruja vershinu,vec:"<<endl;
      cin>>u>>v>>c; 
      ne[v]++;
      e[v][ne[v]]=u;
      w[v][u]=c;
	}





	for (i=1;i<=n;i++) 
	 
 d[i]=INFINITY;

 d[s]=0; 

 for (i=1;i<=n;i++)

 		{
      min=INFINITY;

      for (j=1;j<=n;j++) if ((use[j]==0)&&(d[j]<min)) 
                         {
                         min=d[j];
                         u=j;
                         }

      use[u]=1;

      for (j=1;j<=ne[u];j++)
          {
          v=e[u][j];
          if (d[v]>(d[u]+w[u][v])) {d[v]=d[u]+w[u][v]; p[v]=u;}
      }
      }
      cout<<d[t]<<" ";
      u=t;
      cout<<"Min dlina puti = "<<u;
       while ((u!=s)&&(u!=0)) {u=p[u]; cout<<"-> "<<u; }
      cin>>u;
 return 0;
}
bool check (char str[])
{
int i=0;
while (str[i]!='\0') {if ((str[i]<'0')||(str[i]>'9')) return false; i++;}
return true;
}

// âûâîäèòü âñå âîçìîæíûå âàðèàíòû
// êîððåêòàÿ ðàáîòà ïðîãðàììû
// äèíàìè÷åñêèå ìàññèâû

________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE] (это кнопочка с решёточкой #)
Не забывайте об этом!
Модератор.

[Акоб]

А сказать задачу не судьба?

[Владислав11]

Нахождение кротчайшего пути на графе

[Merovingian]

Такой кривой и непричесанный код)))
Если выводит правильно и один - кратчайший путь, значит, ты изобрел заново алгоритм Дейкстры.
Предлагаю воспользоваться алгоритмом Флойда, он вроде ищет все пути. Т.е. от каждой вершины, до каждой. Реализуется не сложно.

Я за 3 минуты сделал))

PHP код:

for (k = 0; k < n; k++)
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (mass[i][j] > mass[i][k] + mass[k][j])
                dist[i][j] = mass[i][k] + mass[k][j]; 


Каждую иттерацию по k, подставляется вершина, через которую пробуем проложить путь, если он меньше того, что у нас уже есть, то заменяем))
Правда если существуют циклы отрицатльной длинны, то алгоритм требует дополнений...