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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Infinity3000
1058 / 577 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
#1

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

01.11.2011, 22:13. Просмотров 1692. Ответов 5
Метки нет (Все метки)

Здравствуйте!

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

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

Сама задача

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

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

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

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

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

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++)) вот сама задача: заданы 7 городов ...

Поиск самых коротких расстояний между любыми двумя вершинами графа по методу Шимбела - C++
у меня большие проблемы с логикой программирования) поэтому обращаюсь к вам за помощью..... Поиск самых коротких расстояний между любыми...

Задача на рекурсию. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги - C++
Дана матрица размером NxN с расстояниями между городами при наличии прямой дороги между ними. По вертикали содержаться города откуда...

Длина пути между городами - C++
Прошу помощи в решении задачи. Я не могу поняты как это сделать потому прошу вашей помощи. Надо найти путь который прошел...

Количество построенных между городами дорог - C++
Древняя рукопись В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках...

Расстояние между двумя ближайшими городами - C++
Помогите пжалста. В некотором государстве n городов. Найти расстояние между двумя ближайшими городами от города A. Входные данные В...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Infinity3000
1058 / 577 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
02.11.2011, 02:08  [ТС]     АТД Графы. Поиск суммы расстояний между городами. #2
нет ни у кого мыслей и похожего алгоритма??
x1Mike7x
216 / 129 / 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
1058 / 577 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
02.11.2011, 02:45  [ТС]     АТД Графы. Поиск суммы расстояний между городами. #4
Все четко работает)) спасибо! может есть у кого то еще варианты??
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2011, 11:38     АТД Графы. Поиск суммы расстояний между городами. #5
Цитата Сообщение от Infinity3000 Посмотреть сообщение
Задана система двусторонних дорог, где для любой пары городов есть соединяющий их путь. Найти город с минимальной суммой расстояний до остальных городов. Путь между двумя городами в две стороны может быть разным.
Все очень просто:

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

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

Infinity3000, Если Вам нужен вариант только прямых сообщений, то используйте мой алгоритм. Если Вам нужен вариант самых дешевых (и не обязательно прямых) проездов, то используйте алгоритм предложенный x1Mike7x
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2011, 11:41     АТД Графы. Поиск суммы расстояний между городами.
Еще ссылки по теме:

Расстояние между двумя ближайшими городами - C++
Помогите пжалста. Как бы тупо это не звучало, пжалста сделайте эту задачу для меня:wall: В некотором государстве n городов. Найти...

Поиск суммы между элементами массива - C++
Какая сумма элементов массива больше – с первого до максимального элемента, между минимумом и максимумом, или от минимального элемента до...

Найти расстояние между городами на Земле по координатам - C++
на днях дали задание написать программу, которая высчитывает расстояние между городами по координатам. Я пытался ее сделать через формулы...

Vector - найти наименьшее и наибольшее расстояния между городами - C++
// 35_Расстояние.cpp: определяет точку входа для консольного приложения. // #include &quot;stdafx.h&quot; #include...

Найти минимальное количество пересадок между двумя городами - C++
Здраствуйте!Помогите пожалуйста Кратчайший путь. Даны N городов и связи между ними в виде матрицы смежности. Требуется найти...

АТД Стек. Различие между push() и emplace() - C++
Здравствуйте! Расталкуйте пожалуйста в чем заключается различие между двумя методами стека push() и emplace(). на первый взгляд и...


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

Или воспользуйтесь поиском по форуму:
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
02.11.2011, 11:41     АТД Графы. Поиск суммы расстояний между городами. #6
Дискретная математика

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

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