Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 5
1

Алгоритм Флойда

28.04.2013, 00:59. Просмотров 513. Ответов 0
Метки нет (Все метки)

Ребят, помогите! нужно в коде поправить вывод кратчайшего пути, а именно что бы выводило сам кратчайший путь, а не только вершины.
на входе файлик вида
n m
v1 u2 w1
v2 u2 w2
....
где n - количество вершин,m- количество ребер,v - начальная вершина ребра ,u - конечная ,w - вес ребра.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <fstream>
#include <list>
using namespace std;
const int INF = 100500;
 
struct TEdge {
 int x, y, weight;
};//ребро
 
TEdge* ReadFromFile(char* filename,int &n,int &m)
{
 char s[10];
 FILE *f;
 f=fopen(filename,"rt");
 if (f==NULL)
 {
  cout<<"Incorrect filename"<<endl;
  system("pause");
  exit(0);
 }
 fgets(s,10,f);
 sscanf(s,"%d %d",&n,&m);
    TEdge* edges = new TEdge[m];
    for (int i = 0; i < m; i++)
 {
  fgets(s,10,f);
  sscanf(s,"%d %d %d",&(edges[i].x),&(edges[i].y),&(edges[i].weight));
 }
 return edges;
}
 
void PrintMatrix(int n,int** mat)
{
 for (int i=0;i<n;i++)
 {
  for (int j=0;j<n;j++)
   printf("%3d",mat[i][j]);
  printf("\n");
 }
}
 
int** Adjacency_Matrix(int n, int m, TEdge* edges)
{
    int** matrix_nn;
    matrix_nn = new int*[n];
 for (int i = 0; i < n; i++)
  matrix_nn[i]=new int[n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            matrix_nn[i][j] = 0;
    for (int i = 0; i < m; i++)
        matrix_nn[edges[i].x - 1][edges[i].y - 1] += 1;
    return matrix_nn;
}
 
 
 
 
 
int** FloydWarshall(int n,int m,TEdge* e,int** prec,bool &negEdge)
{
 int** w = new int*[n];
    for (int i = 0; i < n; i++)
 {
  w[i]=new int[n];
        for (int j = 0; j < n; j++)
            w[i][j] = 0;
 }
 negEdge = false;
    for (int i = 0; i < m; i++)
 {
  w[e[i].x - 1][e[i].y - 1] = e[i].weight;
//  }
 }
 for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (w[i][j] == 0)
            {
    w[i][j] = INF;
                prec[i][j] = -1;
            }
            else prec[i][j] = i;
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (i == j) w[i][j] = 0;
                else
     if (w[i][j] > w[i][k] + w[k][j])
     {
      w[i][j] = w[i][k] + w[k][j];
      prec[i][j] = prec[k][j];
     }
            }
    }
    return w;
}
 
 
 
void printPath(int* path,int i){
 if (path[i]==-1)
 {
  cout<<i<<" ";
  return;
 }
 printPath(path,path[i]);
    cout<<i<<" ";
}
 
 
 
int main()
{
 int n,
 m;
 TEdge* edges;
    char arrow[5] = "->";
 int** AdjMat;
 char filename[255];
 cout<<"Enter input file name"<<endl;
 cin>>filename;
 edges = ReadFromFile(filename,n,m);
 AdjMat = Adjacency_Matrix(n,m,edges);
 cout<<"Adjacency Matrix :\n";
 PrintMatrix(n,AdjMat);
 int startVert = 0;
 cout<<"Enter start vert:\n";
 cin>>startVert;
 int endVert;
 cout<<"\nEnter end vert:\n";
 cin>>endVert;
 bool flag = false;
 int** prec = new int*[n];
 for (int i=0;i<n;i++)
  prec[i]= new int[n];
 int** dist = FloydWarshall(n,m,edges,prec,flag);
 if (flag) cout<<"Graph has negative edges\n";
 else
 {
  cout<<"Distance Matrix(Floyd Warshall) :\n";
  PrintMatrix(n,dist);
  cout<<endl;
  cout<<"Path from "<<startVert<<" to "<<endVert<<endl;
  if (dist[startVert][endVert]!=INF) printPath(prec[startVert],endVert);
  else cout<<"NO PATH\n";
  cout<<endl;
 }
  cout<<endl;
 system("pause");
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.04.2013, 00:59
Ответы с готовыми решениями:

Алгоритм Флойда
Добрый вечер, помогите исправить ошибки в коде. #include &lt;iostream&gt; #include &lt;time.h&gt; #include...

Алгоритм Флойда Оршала
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой любую матрицу 4*4....

Алгоритм Флойда С++ реализация
Есть такой код класса Помогите, пожалуйста найти по методу Флойда самый короткий путь, он описан в...

Алгоритм Флойда-Уоршела
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.04.2013, 00:59

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Алгоритм Флойда - Уоршелла
не получается реализовать алгоритм Флойда-Уоршелла, вроде все должнен выводить, а выводит или нули...

Алгоритм Флойда–Уоршелла
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++)как сделать так,...

В чем ошибка? Алгоритм Флойда
Не понимаю почему не запускается, может нужна еще кака-набудь библиотека? Программу нашел в...

Алгоритм Флойда-Уоршелла. Графы
Вообщем, требуется найти кратчайший путь между тремя вершинами в дереве со взвешенными ребрами....

Алгоритм Флойда-Уоршалла граф
Собственно мне дан ориентированный граф,в котором вес ребра между вершинами i и j допустим-это шанс...

Алгоритм Флойда (теория графов)
код: int** floid(int** W,int n){ vector&lt;int**&gt;D(n); int** A=new int*; for(int i=0;i&lt;n;i++){...


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

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

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