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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Сообщить одной функции другую http://www.cyberforum.ru/cpp-beginners/thread850492.html
Экспериментирую с функциями, вот решил написать две функции. одна для расчета другая для вывода. Вопрос гду ошибка. Или так просто нельзя делать? #include <iostream> using namespace std; double vklad,stavka,srok; double output(double *result){ double c; cout << "Ведите сумму вклада: "; cin >> vklad; cout << "Введите процент ставки: ";
C++ Сформировать массив данных с помощью структуры. Отсортировать полученный список по полю «год издания» Сформировать массив данных с помощью структуры. Предметная область – список книг в библиотеке (номер по порядку, название, автор, год издания, количество книг). Отсортировать полученный список по полю «год издания». Вывод результатов оформить в виде таблицы. #include<iostream.h> #include<string.h> int main() { http://www.cyberforum.ru/cpp-beginners/thread850491.html
C++ Непонятный Stack Overflow
Здравствуйте, уважаемые форумчане.Столкнулся с непонятной мне проблемой при решении одной лёгкой олимпидной задачи. Вот условие задачи: Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец...
C++ Строки. Замена слова в строке на заданное слово
Задача, ввожу слова в строку потом ввожу слово которое нужно заменить и слово на которое нужно заменить. Т.к с функциями строк плохо знаком моя идея такова если ето возможно.. Я разбиваю строку на слова и в масив строк в каждую ячейку добавляю слово. Введеное слово сравниваю с словом в ячейке и если совпадает заменяю и в конце вывожу свой масив строк) подскажите как лучше сделать и если моя...
C++ Не могу разобраться с шаблонным классом http://www.cyberforum.ru/cpp-beginners/thread850468.html
Привет. Не могу разобраться в нижеизложенной ситуации. Вопрос: почему такая конструкция не работает, и как заставить её работать?template <typename T> struct A { T * a; A( unsigned size ) : a( new T ) {} }; class B { A <char> a; B() {} };
C++ Сортировка методом пузырька массив я задал, а вот сортировку не могу сделать(( #include "stdafx.h" #include <iostream> #include <ctime> #include <cstdlib> #include <iomanip> int main() { const int a=100, b=100; подробнее

Показать сообщение отдельно
Anton18
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 5
28.04.2013, 00:59     Алгоритм Флойда
Ребят, помогите! нужно в коде поправить вывод кратчайшего пути, а именно что бы выводило сам кратчайший путь, а не только вершины.
на входе файлик вида
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");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 09:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru