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

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

Войти
Регистрация
Восстановить пароль
 
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
#1

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

29.04.2013, 21:50. Просмотров 1065. Ответов 3
Метки нет (Все метки)

Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО ЗНАЧЕНИЕ кратчайшего пути, а только по каким вершинам проходит кратчайший путь. Помогите дописать вывод значения кратчайшего пути, буду очень благодарен
значения в коде, как я уже понял, считываются с текстового файла вида
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 байт, 16 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2013, 21:50     Алгоритм Флойда-Уоршела
Посмотрите здесь:

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

Алгоритм Флойда–Уоршелла - C++
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++) как сделать так, чтобы алгоритм нахождения кратчайшего...

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

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

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

В чем ошибка? Алгоритм Флойда - C++
Не понимаю почему не запускается, может нужна еще кака-набудь библиотека? Программу нашел в интернете #include &lt;vcl.h&gt; #pragma...

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

Алгоритм Флойда-Уоршелла (результат работы неправильный) - C++
Задание выглядит так: Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой...

Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. - C++
Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. А л г о р и т м Ф л о й д а Данные: матрица весов...

ошибка у флойда - C++
помогите найти ошибку: #include &lt;fstream&gt; #include &lt;iostream&gt; #include &lt;windows.h&gt; #include &lt;wincon.h&gt; using namespace std; ...

Сортировка всплытием Флойда - C++
Помогите написать программу на С++!!! (Console Application) Очень срочно надо!!!

Нахождение кратчайшего расстояния методом Флойда - C++
Программа спрашивает кол-во вершин . И должно последовательно вводится расстояние между всеми вершинами. НО вводится лишь расстояние...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
30.04.2013, 01:21  [ТС]     Алгоритм Флойда-Уоршела #2
Ребят, может помочь кто?
ForEveR
В астрале
Эксперт С++
7969 / 4731 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 3
30.04.2013, 09:15     Алгоритм Флойда-Уоршела #3
Jenya18, Что имеется ввиду под "само значение"? Дискретная математика
Второе сообщение посмотрите, может поможет.
Jenya18
0 / 0 / 0
Регистрация: 29.04.2013
Сообщений: 13
02.05.2013, 01:55  [ТС]     Алгоритм Флойда-Уоршела #4
Я смотрел все эти темы, у меня не получается. Мой код выводить только вершины, по которым проходит кратчайший путь, а мне нужно что бы вывело именно длину этого пути по всем вершинам

Добавлено через 12 часов 52 минуты
Помогите!!!
Yandex
Объявления
02.05.2013, 01:55     Алгоритм Флойда-Уоршела
Ответ Создать тему
Опции темы

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