Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
#1

Восстановление кратчайшего пути в графе - C++

27.05.2013, 18:26. Просмотров 2191. Ответов 5
Метки нет (Все метки)

Есть алгоритм нахождения кратчайших путей(Флойд), а как восстановить путь как узнать через какие вершины он прошел?туплю прогаю с утра))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<fstream>
main(){
int n,b[101][101],i,j,k,a;
std::ifstream I("input.txt");
std::ofstream O("output.txt");
I>>n;
 
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++){
I>>b[i][j];
a=b[i][k]+b[k][j];
if(b[i][j]>a)
b[i][j]=a;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
O<<b[i][j]<<" ";}O<<"\n";}
 
 
}
Добавлено через 2 часа 2 минуты
http://e-maxx.ru/algo/floyd_warshall_algorithm#3 вот нашел восстановление пути)ток чет туплю как вставить сюда)

Добавлено через 20 часов 5 минут
сделал сам
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int N = points.size();// количество вершин
                            int b[][] = new int [N][N];// матрица смежности
                            int c[][] = new int [N][N];// матрица предков(фаз)
                            
                            for(int i=0;i<N;i++)// инициализируем матрицы 999999- пути не сущ. 0- путь из вершины в саму себя
                                for(int j=0;j<N;j++) {b[i][j]=999999;b[i][i]=0;c[i][j]=0;}
                            
                            for(int i=0;i<rebra.size();i++)// заполняем матрицу смежности текущими весами
                            {                       
                                b[rebra.get(i).getX()-1][rebra.get(i).getY()-1]=rebra.get(i).getV();
                                b[rebra.get(i).getY()-1][rebra.get(i).getX()-1]=rebra.get(i).getV();
                            }
                            
                            for(int k=0;k<N;k++)// алгоритм Флойда
                                for(int i=0;i<N;i++)
                                        for(int j=0;j<N;j++){
                                            int a=b[i][k]+b[k][j];
                                            
                                            if(b[i][j]>a)
                                            {   
                                                
                                                c[i][j]=k;
                                                b[i][j]=a;
                                            }
                                        }
                                                
                            LinkedList <Integer> put = new LinkedList <Integer> ();// связный список вершин входящих в путь
                            
                                int i=p.getX()-1,j=p.getY()-1;
                            while(c[i][j]!=0){//в обратном
                                put.addLast(c[i][j]);
                                j=c[i][j];
                                
                            }
                             i=p.getX()-1;j=p.getY()-1; 
                            while(c[i][j]!=0){
                            if( !put.contains(c[i][j]) )// убираем повторяющиеся вершины
                                put.addFirst(c[i][j]);
                                i=c[i][j];
                                
                            }
                            
                            put.addLast(p.getX()-1);// добавляем начальные вершины
                            put.addFirst(p.getY()-1);
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.05.2013, 18:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Восстановление кратчайшего пути в графе (C++):

Поиск кратчайшего пути на графе - C++
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _itoa. See...

Поиск кратчайшего пути в графе - C++
Добрый вечер! Помогите решить задание пожалуйста: написать программу, решающую задачу в соответствие с вариантом, и вывести результат...

Поиск кратчайшего пути в графе - C++
Задача: отыскать кратчайший путь между двумя заданными вершинами в произвольном ациклическом ориентированном графе с нагруженными ребрами. ...

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

5
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
27.05.2013, 19:01 #2
Mysterion777, смотри, когда происходит релаксация
C++
1
if(b[i][j]>a)
нужно в матрицу кратчайших путей "M" записывать так : M[i][j] = k;
Потом, когда захочешь узнать откуда ты пришёл в вершину j, кратчайшим путём из i, то ответ будет M[i][j];
Тогда, если будет задачи узнать кратчайший путь из i В j тогда : k = j; while (k != i) {cout << k; k = M[i][k]; } cout << k;
Соответственно, изначально матрица M[i][j] = i; для всех i, j;
1
Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
27.05.2013, 19:03  [ТС] #3
Цитата Сообщение от Mysterion777 Посмотреть сообщение
сделал сам
смотрите внимательнее))но ваше решение лучше моего, не проверял на работоспособность, всеравно спасибо за ответ)
2
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
27.05.2013, 19:06 #4
Mysterion777, тогда пишите, что тема закрыта. жирными буквами
0
Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
27.05.2013, 20:49  [ТС] #5
Цитата Сообщение от Ternsip Посмотреть сообщение
Mysterion777, тогда пишите, что тема закрыта. жирными буквами
посомтрите еще подобное алгоритм прима, как восстановить путь?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<fstream>
int n,m,a,b,c,s[101][101],i,j,L[101],k,u,r,h=40000;
using namespace std;
main (){
std::ifstream I("input.txt");
std::ofstream O("output.txt");
 
I>>n>>m;
 
 
for ( i=0;i<n;i++)
for ( j=0;j<n;j++){s[i][j]=h;s[i][i]=0;}
 
for (i=0;i<m;i++){
I>>a>>b>>c;
s[a-1][b-1]=c;
s[b-1][a-1]=c;}
 
 
for(i=0;i<n;i++)
L[i]=s[0][i];
int k2=1;
for(i=1;i<n;i++){
   u=L[1];
    k=1;
     for(j=0;j<n;j++)//ГЁГ§ ýòîé âåðøèГ*Г» ìèГ*ГЁГ¬Г*ëüГ*ûé Гў äðóãèå
      if(L[j]<u&&L[j]){
         u=L[j];
        k=j;}  
     
   r+=L[k];
   
    L[k]=h+1;
     for(j=0;j<n;j++)
      if(s[k][j]<L[j]&&L[j]<h+1){
        
        L[j]=s[k][j];
        
        
        }
  
    }
O<<endl<<r;
 
}
2
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
27.05.2013, 21:07 #6
Mysterion777,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
 
using namespace std;
 
#define forn(i,n) for(int i=1;i<=n;i++)
const int INF = INT_MAX/2;
 
int main()
{
        int n,m;       
        scanf("%d%d",&n,&m);
 
        vector< vector<int> > a(n+1,vector<int>(n+1,INF));
 
        forn(i,m)
        {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                a[x][y] = a[y][x] = z;
        }
       
        vector<int> d(n+1, INF);
        vector<bool> used(n+1,false);
        vector<int> p(n+1,0);
        d[1] = 0;
       
        while (true)
        {
                int mind = INF,mini = 0;
 
                forn(i,n)
                        if (!used[i] && d[i]<mind)
                        {
                                mind = d[i];
                                mini = i;
                        }
                if (mind >=INF/2) break;
               
                used[mini] = true;
                forn(i,n)
                        if (!used[i] && a[mini][i]<d[i])
                        {
                                d[i] = a[mini][i];
                                p[i] = mini;
                        }
        }
 
        int sum = 0;
        forn(i,n)
                if (p[i] != 0) sum += a[i][p[i]];
        printf("%d\n",sum);
        forn(i,n)
                if (p[i] != 0)
                printf("%d %d\n",i,p[i]);
}
1
27.05.2013, 21:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2013, 21:07
Привет! Вот еще темы с ответами:

Нахождение кратчайшего пути - C++
Нужно сделать программу,чтоб она находила кратчайший путь от города 1 до города 2 на карте. Как реализовать в коде не знаю, помогите. ...

Поиск кратчайшего пути (рекурсия) - C++
Помогите пожалуйста. Пусть имеется n городов. Некоторые из них соединены дорогами известной длины. С помощью рекурсии найти Кратчайшие...

Задача нахождения кратчайшего пути - C++
Никак не могу понять почему в таких типах задач у меня ошибка. Помогите найти ошибку, и если сможете объясните её. Условие ...

Поиск кратчайшего пути на клетчатом поле. - C++
Дано клетчатое поле (допустим n x n). На некоторые клетки наступать нельзя. Дана начальная клетка, дана конечная клетка. Надо найти...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru