Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

01.11.2011, 22:13. Просмотров 1766. Ответов 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;
}

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

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


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

Вывести таблицу расстояний между городами - C++
в принципе я знаю алгоритм решения ее)) но я не смог перенести свой алгоритм на c++)) вот сама задача: заданы 7 городов ...

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

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

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

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

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

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

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

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

Infinity3000, Если Вам нужен вариант только прямых сообщений, то используйте мой алгоритм. Если Вам нужен вариант самых дешевых (и не обязательно прямых) проездов, то используйте алгоритм предложенный x1Mike7x
1
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
02.11.2011, 11:41 #6
Дискретная математика

Второе сообщение - алгоритм Флойда-Уоршалла.
1
02.11.2011, 11:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2011, 11:41
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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