Форум программистов, компьютерный форум CyberForum.ru

Поиск отрицательного цикла (контура) в графе - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Представление из бит в байт http://www.cyberforum.ru/cpp-beginners/thread1176083.html
Вообще такая беда как представить биты в то что они были сначала,вот так я представляю байт в битах с помощью маски,а как обратно не знаю for (int i = 0; i < N; i++){ for (int j = 0, byte = buf; j < 8; byte <<= 1, j++){ byte & 0x80 ? bit = 1 : bit = 0; k++; }
C++ Подключение Dll на С++ к Java и С# Добрый день. Подскажите, пожалуйста куда копать: надо создать DLL на С++ с функциями, структурами и классом так, чтобы её потом можно было подключить к Java и С#. Как подключить её к другому С++ приложению - я понимаю. Либо статика либо хэдер, который у меня есть. А вот как это всё импортировать в Java и С# я не представляю, так как кроме обычных типов, там есть ещё и классы и структуры. ... http://www.cyberforum.ru/cpp-beginners/thread1176075.html
Неработает проверка на ввод enter C++
По логке кода, при нажатии на ентер цыкл должен оборватся, но этого не происходит, почему? char login; char pass; char fio; cout<<"Registration: \n"; cout<<"Write login (max 10 length)\n\n"; for (int i = 0; i < 9; i++)
В массиве найти элемент больше заданного, удалить каждый пятый и последние три заменить на ср. арифметическое C++
1-Дан одномерный массив Xn. Найти первый элемент массива, значение которого ,больше А. Удалить каждый пятый элемент. Последние три элемента массива заменить на значение среднего арифме-тического элементов исходного массива с четными номерами.
C++ Написать процедуру обмена столбца и строки двухмерного массива http://www.cyberforum.ru/cpp-beginners/thread1176058.html
Написать процедуру обмена столбца и строки двухмерного массива. С ее помощью поменять местами те строки и столбцы, первые элементы которых совпадают.
C++ Ошибка в создании массива объектов Есть класс Circle, в котором определены переменные для координат Х и У и радиуса окружности (здесь всё правильно, вроде бы). При компиляции на класс и реализацию компилятор не ругается (Dev-C++), а вот в основной программе массив, похоже, не создаётся. Это класс: #if !defined CIRCLE_H #define CIRCLE_H #include <iostream> using namespace std; class Circle{ private: double coordX,... подробнее

Показать сообщение отдельно
Snegovik
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 2
14.05.2014, 20:16     Поиск отрицательного цикла (контура) в графе
Всем привет! Помоги пожалуйста с программой!

Имеется алгоритм Флойда для поиска кратчайшего пути. Нужно найти кратчайший путь и его сумму. Это всё работает.
Но! Если в графе имеется отрицательный цикл, то нужно сообщить об этом и вывести этот самый цикл.

Например, дан граф с отрицательными рёбрами и причём с циклом:

Поиск отрицательного цикла (контура) в графе

Так как алгоритм Флойда для отрицательного цикла не примененим, то нужно сообщить об этом и вывести путь отрицательного цикла. В данном графе он будет равен: 1->2->1

На вход подаётся матрица смежности (mass), затем я её модифицирую:
C++ (Qt)
1
2
3
4
5
6
7
8
for (int i = 0; i < n; ++i)
          for (int j = 0; j < n; ++j) {
              if (mass[i][j] == 111) //если ввёл 111, то я подразумеваю бесконечность
                  mass[i][j] = inf;
              if (i==j) mass[i][j]=0; //обнуление главной диагонали
              D[i][j] = mass[i][j];   //модифицированная матрица смежности [B]D[/B]
              par[i][j] = i;             //заполнение матрицы предков
}

Сам алгоритм Флойда. GR=D; par=parents

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i)
              for (int j = 0; j < V; ++j)
                    if (GR[i][j] > GR[i][k] + GR[k][j]) {
                          GR[i][j] = GR[i][k] + GR[k][j];
                          parents[i][j] = parents[k][j]; 
                    }
        for (int i = 0; i < V; ++i) {
              for (int j = 0; j < V; ++j) {
                  cout <<GR[i][j]<<" ";
              } cout<<endl;
        }
        cout<<endl;
}
Ну и потом у меня вывод кратчайшего пути:
C++ (Qt)
1
2
3
4
5
6
 if (D[s][f] < inf)) {    
        cout<<"Длина минимального пути: ";
        cout << D[s][f] << endl<<endl;
        cout<<"Кратчайший путь: ";
        Travel(f,s,par);
  }
Функция Travel. На входе в функцию: v-конечная вершина вершина, s1-начальная, parent - матрица предков.

C++ (Qt)
1
2
3
4
5
6
7
8
9
void Travel(int v, int s1, int parent [][MAXIV]) { 
  if (v == s1) {
        cout << v + 1 << " -> ";
  }
  else {
        Travel(parent[s1][v], s1, parent);
        cout << v + 1 << " -> ";
  }
}
Как вот теперь найти отрицательный цикл и самое главное (!) его путь, если такой граф попадётся? (как в примере?). Заранее спасибо)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 00:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru