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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Элементы, расположеные на главной диагонали, в первых 3 строках выше диагонали и в последних 2 строках ниже диагонали переместить в одномерный массив http://www.cyberforum.ru/cpp-beginners/thread852363.html
Нужно элементы расположены на главной диагонали, в первых 3 строках выше диагонали и в последних 2 строках ниже диагонали переместить в одномерный массив. P.S. help #include <stdio.h> #include <conio.h> void main() { int a; int b;
C++ Программа Жизнь Вообщем... Что-то не могу сообразить с программой... Реализовать алгоритм игры «жизнь». Дано двумерное поле клеток, каждая из которых либо содержит организм (1), либо пуста (0). Каждая клетка проверяет состояние своих соседей (их 8) и изменяет своё по правилам: Живая клетка, вокруг которой < 2 живых клеток, умирает от одиночества. Живая клетка, вокруг которой есть 2 или 3 живых клеток,... http://www.cyberforum.ru/cpp-beginners/thread852355.html
Поиск последовательности в массиве символов C++
есть массив ascii символов мне нужно там найти последовательность (строку) есть какие-нибудь функции для поиска последовательности. в ручную я уже реализовал.
C++ Интеграция скомпилированного Fortran - приложения в программу на C++
Как можно использовать в программе написанной на с++ откомпилированное fortran приложение? Т.е. поступают входные данные в программу написанную на с++, она их передает в откомпилированную программу написанную на фортране, а та в свою очередь делает вычисления, и возвращает выходные данные в программу на с++, и далее программа на с++ продолжает вычисления... Буду рад всему, литература, ссылки...
C++ Слияние массивов http://www.cyberforum.ru/cpp-beginners/thread852289.html
Получить массив С(k), упорядоченный по возрастанию, путем слияния массивов A(n) и B(m), упорядоченных перед этим по возрастанию, где k = n + m
C++ Какой лучше комрилятор? Прошу извинения сразу. Тема заезженная .Какой компилятор лучше ? И какую версию компилятора выбирать анг. или русск.? подробнее

Показать сообщение отдельно
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
29.04.2013, 21:50     Алгоритм Флойда-Уоршела
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО ЗНАЧЕНИЕ кратчайшего пути, а только по каким вершинам проходит кратчайший путь. Помогите дописать вывод значения кратчайшего пути, буду очень благодарен
значения в коде, как я уже понял, считываются с текстового файла вида
n m
v1 u1 w1
v2 u2 w2
.....
n - колво вершин, m - кол-во ребер, v1,v2 ... - начальная вершина, u1,u2...- конечная вершина. 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
#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("%8d",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");
}
Вложения
Тип файла: txt graph2.txt (127 байт, 12 просмотров)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 11:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru