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

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

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

Метод прямой прогонки. Динамическое программирование - C++

12.11.2013, 17:28. Просмотров 1163. Ответов 1
Метки нет (Все метки)

надо написать прогу, которая искала бы кратчайший путь из одного конца неориентированного графа в другой путем прямой прогонки. я реализовал граф методом списка дуг. проверил(немного коряво но все таки...) не идет ли в в вершину лишь одна дуга и все... как реализовать формулы понятия не имею. Может быть поможете? Если не кодом, то хотя бы словесно опишите как и что.
P.S. формула кратчайшего пути методом прямой прогонки выглядит как-то так:
(Кратчайший путь к узлу) = min({Кратчайший путь к предыдущему узлу+расстояние от предыдущего до этого узла})={2+3=5
3+5=8
2+4=6} Кратчайший путь к узлу = 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
//  Алгоритмы V 1.0.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL,"");
    int i,j, Graf[4][14]={/*из какой вершины начинается дуга [0]*/1,1,1,2,3,3,4,5,5,6,6, 7, 8, 9,
                           /*в какой вершине заканчивается [1]*/   2,3,4,5, 5,6,6,7, 8,8,9,10,10,10,
                           /*вес дуги [2]*/                        5,7,9,4,10,8,5,6,10,4,3, 7, 5, 6 };
    
////////////////////Построение графа////////////////////////////////////////
    
    for (i=0;i<3;i++)
    {
        
     for (j=0;j<14;j++)
     {
        
        printf("%5d",Graf[i][j]);
        
     }
     
      printf("\n");
        
    }
 
    
    printf("\n");
    
////////////////////Проверка не идет ли в вершину только одна дуга////////////////////////////////
    for (j=0;j<14;j++)
    {
        printf("%5d",Graf[1][j]);
        
 
        if (Graf[1][j]!=Graf[1][j+1] )
        {
             Graf[3][j]=Graf[2][j];
             
            
             
         }
 
     }
    printf("\n");
    printf("\n");
    printf("\n");
    for (j=0;j<14;j++)
    {
        printf("%5d",Graf[3][j]);
            
    }
     printf("\n");
system("pause");
      return 0;
 
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2013, 17:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Метод прямой прогонки. Динамическое программирование (C++):

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

Метод динамическое программирование - C++
Помогите пожалуйста с задачей.Дано натуральное число N, не превосходящее 1000. За один ход разрешается поделить его на 2 или на 3 (если...

Метод прогонки - C++
Здравствуйте, пытаюсь реализовать метод прогонки, не могу проверить работу, не понимаю как заполнять, и как сделать массив чтобы высчитывал...

метод прогонки С++ - C++
Запрограммировать краевую задачу методом прогонки(тридиагональнои матрицы) Добавлено через 4 минуты Очень срочно надо^_^ ...

Метод обратной прогонки - C++
Нужно реализовать метод обратной прогонки на с++.МОЖНО ВЗЯТЬ ЛЮБОЙ ПРИМЕР.КТО МОЖЕТ ПОМОГИТЕ!!

Метод прогонки - исправить код - C++
Всем здравствуйте!!! Друзья, передо мной стоит задача, программная реализация метода прогонки. У меня есть код, который реализует это...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
adam999
0 / 0 / 0
Регистрация: 10.04.2013
Сообщений: 23
10.12.2013, 21:14 #2
Иван,если есть поставь да полную версию программы .....тож срочно нужна....
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2013, 21:14
Привет! Вот еще темы с ответами:

Метод прогонки для СЛАУ - C++
Народ, я почти умер. Писал метод прогонки, работает неправильно, выдает что-то близкое, но неточно. код: #include...

Метод прогонки с разделяемой памятью на CUDA - C++
Здравствуйте. Есть метод прогонки на CUDA для глобальной памяти. Не могу реализовать то же самое для разделяемой ,пишет ошибки и всё. ...

Метод прогонки краевых задач для обыкновеных дифф. уравнений - C++
k(x)=sin^2(x)+1 q(x)=cosx f(x)=e^x \beta1=1 \beta2=1

что делает эта программа распишите пожалуйста? это ведь метод прогонки? - C++
что делает эта программа распишите пожалуйста? это ведь метод прогонки? #include &lt;cstdio&gt; #include &lt;math.h&gt; #include &lt;iostream&gt; ...


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

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

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