C++ Топологическая сортировка с поиском кратчайшего пути

[_Санек_]

Входные данные: матрица весов "неверно" ориентированного графа(0 - если дуги нет или же дуга входит, а не выходит из вершины i в j; число - вес дуги, выходящей из вершины i в j). Сортировка с помощью поиска в глубину выводит по сути отсортированные вершины графа. Подскажите, как найти кратчайшее расстояние от первой до последней вершины и по возможности выдать через какие вершины проходит этот маршрут?

#include <iostream>
using namespace std;

  int s[1000]; // топологически упорядоченная последовательность вершин

  int u[1000]; /* флаги сортировки:
    0 - вершина не упорядочивалась,
    1 - упорядочена,
   -1 - в процессе упорядочения */

  struct kletka
  {
      int s;   // смежность: 0 - нет дуги, 1 - есть дуга
      int v;   // вес дуги
  };

  kletka Matr[100][100]; // матрица смежности(весов)

  int n; // количество вершин
  int k; // счетчик
 /* int sum; */

// Алгоритм топологической сортировки
bool topsort(int i)
{
 // cout<<endl<<"I="<<i<<" K="<<k;
  int j;
  if (u[i]!=0)
  {
    u[i]=1;
    return true; // если уже упорядочена - успех, иначе - неудача
  }
  u[i]=-1; // начали упорядочивать вершину i
  int q=0;
  for(j=0;j<n;j++)
    if (Matr[i][j].s!=0)
    {
       /* q=q+1;
        if (q==1)
          sum+=Matr[i][j].v; */
      if (! topsort(j)) // рекурсия
      {
        return false;   // неудача - есть цикл
      }
    }
  k=k+1;
 // cout<<endl<<"K2="<<k;
  s[k]=i;
 // cout<<endl<<"spisok="<<s[k];
  u[i]=1;      // вершина i упорядочена
  return true; // успех
}


int main()
{
  int i,j;
  cout<<"Enter chislo vershin"<<endl;
  cin>>n;
  cout<<endl<<"Enter matricu smeshnosti"<<endl;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      {
        cout<<i+1<<" to "<<j+1<<" =";
        cin>>Matr[i][j].v;  // считываем вес дуги
        if (Matr[i][j].v>0) // если вес больше нуля, значит дуга есть
            Matr[i][j].s=1;
        else
            Matr[i][j].s=0; // иначе нет дуги
      }
  cout<<endl<<"Initial data"<<endl;
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
        cout.width(5);
        cout<<Matr[i][j].v;
    }
    cout<<endl;
  }
  k=-1;
  for(i=0;i<n;i++) // обнулим флаги упорядочивания
      u[i]=0;
  sum=0;
  for(i=0;i<n;i++)
  if (! topsort(i))
  {
    cout<<"Impossible"<<endl;
    return 0;
  }
  cout<<endl<<"Result sortirovki"<<endl;
  int c=0;
  for(i=k;i>=0;i--) // вывод упорядоченной последовательности
  {
      c++;
      cout<<endl<<c<<" vershinoy dolshna byt vershina "<<s[i]+1;
  }
 /* cout<<endl<<"Summa= "<<sum; */
  return 0;
}