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

Нахождение кратчайшего пути от одной вершины графа до другой - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Рекурсия: получить число, цифры в котором будут расположены в обратном порядке http://www.cyberforum.ru/cpp-beginners/thread38798.html
Нужно получить с помощью рекурсивной функции число, символы в котором будут расположены в обратном порядке. Например 123 получим 321. Вот что у меня получилось: #include <iostream> #include...
C++ Описать функцию, которая изменяет заданную строку следующим образом задача:Описать функцию, которая изменяет заданную строку следующим образом: сначала записывает все элементы с четными индексами, а затем все элементы с нечетными индексами ( с сохранением их... http://www.cyberforum.ru/cpp-beginners/thread38778.html
Объясните принцип действия алгоритма!!! C++
Это задача о сумме подмножеств, нужно найти элементы массива сумма которых равно нулю{14,-7,-10,4,3, 5, -19, -12, 9, 6}; #include "stdafx.h" #include <math.h> #define N 10 int summ(int l, int *a)...
C++ Постраничный вывод текста
У меня есть функция вывода содержимого файла на экран. И задаётся максимальное количество строк на одну страницу 21. И если у меня на последней странице должно остаться меньше чем 21 строчка, то мне...
C++ Заменить прописные буквы строчными http://www.cyberforum.ru/cpp-beginners/thread38742.html
у меня есть прога заменяющая определенные символы(.и пробел) из одного текстового файла в другой. Нужно ее переделать так чтобы прописные буквы заменялись на строчные вот прога: #include<stdio.h>;...
C++ Продолжаем спасать мир))) Помогите плз) чтобы получить итоговую нужно сдать 3 проги по С++. Сделать их сам не могу( не было на этих темах, парился в военкомате, по поводу отсрочки, будь она не ладна( Спасайте) Осталось 2 дня,... подробнее

Показать сообщение отдельно
exe-dealer
301 / 154 / 4
Регистрация: 07.06.2009
Сообщений: 538
07.06.2009, 17:37
гугли алгоритм дейкстры


могу на C# только показать, у меня работало
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
using System;
using System.Collections.Generic;
using System.IO;
 
namespace dijkstra
{
    public static class program
    {
        public static int input(ref StreamReader stream)
        {
            char next;
            do { next = (char)stream.Read(); } while (!(char.IsDigit(next) || next == '-'));
            string s = "";
            while (char.IsDigit(next) || next == '-') { s += next; next = (char)stream.Read(); }
            return int.Parse(s);
        }
 
        internal static void Main()
        {
            StreamReader fr = new StreamReader("input.txt");
            int n = Convert.ToInt32(fr.ReadLine());
            int[,] c = new int[n, n];
 
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    c[i, j] = input(ref fr);
                    if (c[i, j] == 0) { c[i, j] = int.MaxValue; }
                }
            }
            fr.Dispose();
 
            int s/*старт*/= 6 - 1, dest = 5 - 1;
 
            int[] d/*расстояние от начала до вершины*/ = new int[n], p/*предок*/ = new int[n];
            bool[] f = new bool[n];
 
            //инициализация
            for (int i = 0; i < n; i++) { p[i] = s; d[i] = c[s, i]; }
            f[s] = true;
            p[s] = -1;
 
            for (int i = 0; i < n - 1; i++)
            {
                /*находим среди непомеченых вершин ту, путь от 
                  корня в которую на данный момент минимальный*/
                int k = 0, mindist = int.MaxValue;
                for (int j = 0; j < n; j++) { if (!f[j] && mindist > d[j]) { mindist = d[j]; k = j; } }
 
                f[k] = true; /*помечаем эту вершину*/
 
                /*обновление кратчайших путей*/
                for (int j = 0; j < n; j++)
                {
                    if (c[k, j] == int.MaxValue) { continue; } //есть ли ребро k--j
                    int l = d[k] + c[k, j];
                    if (!f[j] && d[j] > l) { d[j] = l; p[j] = k; }
                }
            }
 
 
            int prev = dest; string path = "";
            for (; ; )
            {
                path = (prev + 1) + " " + path;
                if (prev == s) { break; }
                prev = p[prev];
            }
 
            Console.WriteLine(path + "\n" + d[dest]);
            Console.ReadLine();
        }
 
    }
 
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru