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

АТД Графы. Поиск суммы расстояний между городами. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Infinity3000
 Аватар для Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
01.11.2011, 22:13     АТД Графы. Поиск суммы расстояний между городами. #1
Здравствуйте!

Нужна помощь!

Всем известная задача и в сети конечно много разнообразных тем! но не одна из них не доведена до логического завершения!!!

Сама задача

Задана система двусторонних дорог, где для любой пары городов есть соединяющий их путь. Найти город с минимальной суммой расстояний до остальных городов. Путь между двумя городами в две стороны может быть разным.

Я так понимаю нужно от каждого города находит расстояния до остальных городов и суммировать их, и сумму заносить в массив, потом с другим городом точно так и так далее!!

Потом найти минимальный элемент в массиве и его позицию, где позиция и есть искомый город!

Возможно я ошибаюсь!!

На данный момент я загружаю матрицу смежности из файла и по ней строю список инцидентности которая показывает с какого города в какой можно доехать!! (опирался на одну из тем этого форума)
осталось найти сумму расстояний до городов и из них минимальный!

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
#include <iostream>
 
using namespace std;
 
struct row
{
        int num;
        row *next,*colum;
};
 
int outmas(int n, int **mas)
{
        int i,j;
        cout<<'№'<<' ';
        for(i=1; i<=n; ++i)
                cout << i <<' ';
        cout<<endl;
 
        for(i=0; i<n; ++i)
        {
                cout << i+1 <<' ';
                for(j=0; j < n; ++j )
                        cout<<mas[i][j] <<' ';
                cout<<endl;
        }
        return 0;
}
 
row *convert(int **mas, int n, row *top)
{
        int i,j;
        row *p,*t,*c;
        p = new row;
        p->num = 1;
        p->next = NULL;
        p->colum = NULL;
        top = p;
        for(i = 2; i <= n; ++i)
        {
                t = new row;
                t->num = i;
                t->next = NULL;
                t->colum = NULL;
                p->next = t;
                p = t;
        }
        t = top;
        p = top;
        for(i = 0; i < n; ++i)
        {
                {
                        for(j=0;j<n;++j)
                                if(mas[i][j]==1)
                                {
                                        c=new row;
                                        c->num=j+1;
                                        c->next=NULL;
                                        c->colum=NULL;
                                        p->colum=c;
                                        p=c;
                                }
                                t=t->next;
                                p=t;
                }
        }
        return top;
}
 
int outspis(row *top)
{
        row *p,*t;
        p=top;
        t=p->colum;
        while(p)
        {
                cout<<p->num<<"\t---->\t";
                while(t)
                {
                        cout<<t->num<<'\t';
                        t=t->colum;
                }
                p = p->next;
                if(p)
                        t = p->colum;
                cout<<endl;
        }
        return 0;
}
 
int main()
{
        setlocale(LC_ALL,"Rus");
 
        FILE *in = fopen("in.txt","r");
       
        int i, j, n, **mas;
        
        row *top = NULL;
 
        fscanf(in,"%d",&n);
 
        mas = new int *[n];
       
        for(i = 0; i < n; ++i)
        {
                mas[i] = new int [n];
                
                for(j = 0;  j < n; ++j)
                        fscanf(in,"%d",&mas[i][j]);
        }
 
        outmas(n,mas);
 
        top = convert(mas,n,top);
        
        cout << "\nСписок инцидентности:\n"<<endl<<"Города\t---->\tКуда можно поехать\n"<<endl;
        
        outspis(top);
        
        system("PAUSE >> null");
        delete []mas;
        fclose(in);
        return 0;
}

возможно такой ход решения не правильный!

Если есть у вас уже готовые алгоритмы решения, скиньте пожалуйста! исключительно для самообучения, не каких корыстных целей!


Спасибо!!
Миниатюры
АТД Графы. Поиск суммы расстояний между городами.  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2011, 22:13     АТД Графы. Поиск суммы расстояний между городами.
Посмотрите здесь:

Поиск самых коротких расстояний между любыми двумя вершинами графа по методу Шимбела C++
C++ Найти минимальное количество пересадок между двумя городами
C++ Задача на рекурсию. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги
Расстояние между двумя ближайшими городами C++
C++ Расстояние между двумя ближайшими городами
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Infinity3000
 Аватар для Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
02.11.2011, 02:08  [ТС]     АТД Графы. Поиск суммы расстояний между городами. #2
нет ни у кого мыслей и похожего алгоритма??
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
02.11.2011, 02:25     АТД Графы. Поиск суммы расстояний между городами. #3
Есть алгоритм Флойда-Уоршелла, который обрабатывает матрицу смежности и выдает матрицу, в которой для каждой пары вершин будет содержаться минимальный путь между ними.
Вот примерный код:
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
#define M 123456789
 
int main()
{
    int V_min, TS = M, S, N, A[100][100] = {};
    std::cin >> N; // Ввод количества вершин
    // Ввод матрицы смежности
    for ( int i = 0; i < N; ++i )
        for ( int j = 0; j < N; ++j )
        {
            std::cin >> A[i][j];
            if ( A[i][j] == 0 )
                A[i][j] = M;
        }
    // Алгоритм Флойда-Уоршелла
    for ( int k = 0; k < N; ++k )
        for ( int i = 0; i < N; ++i )
            for ( int j = 0; j < N; ++j )
                A[i][j] = std::min( A[i][j], A[i][k] + A[k][j] );
    // Ищем вершину с минимальной суммой
    for ( int i = 0; i < N; ++i )
    {
        S = 0;
        for ( int j = 0; j < N; ++j )
            S += A[i][j];
        if ( S < TS )
        {
            TS = S;
            V_min = i;
        }
    }
    std::cout << V_min // вывод города с минимальным расстоянием ( нумерация с 0 )
}
Infinity3000
 Аватар для Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
02.11.2011, 02:45  [ТС]     АТД Графы. Поиск суммы расстояний между городами. #4
Все четко работает)) спасибо! может есть у кого то еще варианты??
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2011, 11:38     АТД Графы. Поиск суммы расстояний между городами. #5
Цитата Сообщение от Infinity3000 Посмотреть сообщение
Задана система двусторонних дорог, где для любой пары городов есть соединяющий их путь. Найти город с минимальной суммой расстояний до остальных городов. Путь между двумя городами в две стороны может быть разным.
Все очень просто:

Цитата Сообщение от Infinity3000 Посмотреть сообщение
На данный момент я загружаю матрицу смежности из файла
Потом ищете суммы строк этой матрицы. Номер строки с минимальной суммой и будет ответом.

Добавлено через 1 час 32 минуты
Infinity3000, сейчас еще раз перечитываю тему и задаюсь одним вопросом. Может быть я здесь и не прав.
Суть:
если из города А в город Б стоимость пути равна 50. А из города А в город С дорога стоит 10 и из города С в город Б дорога стоит 10. То из города А в город Б можно проехать напрямую (проезд будет стоить 50), или можно проехать через город С (проезд будет стоить 20).

Infinity3000, Если Вам нужен вариант только прямых сообщений, то используйте мой алгоритм. Если Вам нужен вариант самых дешевых (и не обязательно прямых) проездов, то используйте алгоритм предложенный x1Mike7x
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
02.11.2011, 11:41     АТД Графы. Поиск суммы расстояний между городами. #6
Дискретная математика

Второе сообщение - алгоритм Флойда-Уоршалла.
Yandex
Объявления
02.11.2011, 11:41     АТД Графы. Поиск суммы расстояний между городами.
Ответ Создать тему
Опции темы

Текущее время: 19:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru