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

Алгоритм Дейкстры - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Где найти следующую ступень знаний по С++? http://www.cyberforum.ru/cpp-beginners/thread855410.html
Дело в том, что я уже давно заинтересован изучением C++, не понимаю почему, но именно к нему тянет :). Ладно дело не в том куда я держу свой путь, а в том что я не могу продолжить сдвиг с этого места. я долгое время ищу новых знаний, но всё не в том направлении... Я уже безошибочно могу писать задачки такого типа без шпаргалок и т.д. Я не хочу останавливаться на этом и желаю продолжать...
C++ Кодирование файла Задача написать часть полиморфного вируса для курсовой. Т.е нужно подать нашей программе на вход файл она должна зашифровать его по случайному ключу расшифровать и исполнить. 1 Вопрос как можно зашифровать? 2 Как его исполнить? http://www.cyberforum.ru/cpp-beginners/thread855399.html
Двоичное дерево Хаффмана C++
Дана некоторая последовательность данных...(то есть набор каких то значений)...этот набор представляет из себя набор конечных потомков двоичного дерева....например если набор из двух элементов то всего 1 уровень у дерева если набор из 4 элементов то два уровня ...собственно вопрос в том как программно реализовать построение дерева на основе конечных потомков...(нужно для метода кодирования...
Эйлеровы циклы C++
Ребят, помогите с задачкой. на входе есть ориентированный граф, который задается файликом вида n m v1 u1 v2 u2 ... vm um где n - кол-во вершин графа, m - кол-во ребер, v - начальная вершина ребра, u конечная, можно сказать что граф задается списком ребер. Нужно: найти Эйлеровы циклы в графе и вывести их на экран, если нету циклов тогда найти Эйлеровы маршруты в графе.
C++ расстояние от окружности к ломаной? http://www.cyberforum.ru/cpp-beginners/thread855370.html
написать функцию: даны координаты 20 точек ломаной, найти три круга, которые находятся дальше от нее и три ближайших окружности. есть координаты центров окружностей и их радиус, количество кругов неопределенная, но больше 7. ломаная задана объектами класса линия окружности являются объектами класса окружность это все условие, поэтому алгоритм поиска не определен
C++ Дана сторка содержащая полное имя файла Дана строка содержащая полное имя файла. выделить из этой строки имя последнего каталога. если файл содержится в корневом каталоге то вывести первую букву каталога подробнее

Показать сообщение отдельно
eugrita
3 / 4 / 0
Регистрация: 18.11.2009
Сообщений: 405
06.05.2013, 08:54     Алгоритм Дейкстры
вот простая под C++ практически годится под C если заменить операторы типа
for(int i=....). Пара фунций - печать массива и чтение исх данных из файла - для удобства работы
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
#include <math.h>
#include <stdio.h>
#include <conio.h>
const float INF = 30000;
float ** a;  int *pr;
 void readDan(int *n) {//чтение из файла матрицы
  int m; FILE * f=fopen("dan.txt","r");
if (f==NULL)
{ printf("Error!!! File not found! Press any key to exit");getch();return;}
  fscanf(f,"%i",&m);
  a=new float *[m];
  for (int i=0;i<m;i++)
    for (int j=0;j<m;j++)
       a[i]=new float[m];
  for (int i=0;i<m;i++)
       for (int j=0;j<m;j++)
       {
        fscanf(f,"%f",&a[i][j]);
        if (a[i][j]==-1) a[i][j]=INF;
       }
 fclose(f);  *n=m;
                     }
 void printA(int n) {
   for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++)
      if (a[i][j]==INF) printf(" * ");
      else printf("%2.0f ",a[i][j]);
     printf("\n");
                               }
                    }
 
 void ShortPth(int n,int n1,int n2)   //n1-N нач верш. n2-конечная ,n-кол верш
 {//алг Дейкстры по маnh.Нах кратч расст по паре вершин графа до .
   float  *D; bool *flag;
     pr=new int[n]; D=new float[n];flag=new bool[n];
    for (int i = 0; i < n; i++)
       { pr[i] = n1; flag[i] = false; D[i] = a[n1][i]; }
    //Пока известно только одно расст:от верши nach  до нее же, равное 0.
    flag[n1] = true;    pr[n1] = 0;
    for (int i = 0; i < n - 1; i++) {//i
        int k = 0; float minras = 30000;
        // Находим минимальное расстояние до непомеченных вершин
        for (int j = 0; j < n; j++)       {//j
            if (!flag[j] && minras > D[j])
                  { minras = D[j]; k = j;}
                                          }//j
        flag[k] = true;  // Вершина k помечается просмотренной
        for (int j = 0; j < n; j++)      {//j
    //Если для верш j еще не найдено кратч расст от нач. и из вершины k по дуге A[k][j]
    //путь в j короче чем найденное ранее, то запоминаем его.
            if (!flag[j] && D[j] > D[k] + a[k][j])
                 { D[j] = D[k] + a[k][j];pr[j] = k;}
                                         }//j
                                     } //i
    printf("Rasstoyaniya ot %d do %d: %f\n", n1, n2, D[n2]);
 /*Выв путь задом наперед: в кажд эл масс pr хр N предыд яч-верш кратч пути.Напр,предыд верш для верш 5=pr[5]*/
        printf("\npath: from %d to %d: ", n2 , n1);
        int j=n2; printf("%d ", j);
        while (1==1) {
           j = pr[j];printf("%d ", j);
           if (j==n1) break;
                     }
 }
void main()
{  char c; int n,N1,N2;//n-кол верш
    readDan(&n);
    printf("load graph n=%i A=\n",n);printA(n);
    do {
    if(c=='0') return;
    printf("Nstart=? Nfin=? (ot 0 do %i)\n",n-1); scanf("%i %i",&N1,&N2);
    ShortPth(n,N1,N2);
    printf("\nEXIT-0\n");scanf("%c",&c);
       }  while(1==1);
}
 
Текущее время: 00:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru