Граф на C

Тема в разделе "Общие вопросы по С и С++", создана пользователем -, 12 янв 2009.

Статус темы:
Закрыта.
  1. Гость

    Помогите пожалуйста, надо завтра здавать....

    Надо найти кратчайший путь во взвешеном графе, чтобы в файле мы могли забить таблицу смежности с весами графов, и в другом файле был показан кратчайший путь.

    вот у мну есть модуль по нахождению кратчайшего пути но до конца доделать не получается...

    Код (Text):
     const int INF = 100*1000*1000;

    int main()
    {
    // считываем матрицу графа
    int n;
    cin >> n;
    vector < vector<int> > g (n, vector<int> (n));
    for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
    {
    int t;
    cin >> t;
    g[i][j] = t ? t : INF;
    }


    // храним две матрицы: для текущего шага и от предыдущего шага
    vector<vector<int> > d (n), d2;
    d2 = g;
    for (int i=0; i<n; i++)
    d[i].resize (n+1);
    for (int k=0; k<n; k++)
    {
    for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
    d[i][j] = min (d2[i][j], d2[i][k]+d2[k][j]);
    d.swap (d2);
    }
    d.swap (d2);

    // выводим результат
    for (int i=0; i<n; i++)
    {
    for (int j=0; j<n; j++)
    cout << (d[i][j]<INF ? d[i][j] : 0) << ' ';
    cout << endl;
    }
    }
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей