Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Перевод с языка с++ в с#

60K
12 мая 2010 года
Gerasym
2 / / 12.05.2010
Код:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define P 60
#define MAX 1000               //машинный эквивалент бесконечности

int m;                       // матрица для вычисления кратчайшего пути и его длины
int v;                       // матрица для нахождения всех возможных путей между данными вершинами в графе не пеpесекающиеся по pебpам
int D, G, W,Z;
int N,M,S,F;
int a,b,c;
int i,j,k,l,h,f;
 
void GRAF (int m) {         // функция нахождения кратчайшего пути
 
   for (i=1 ; i<=N ; i++ )
    D = m;               // массив , содержащий расстояния от заданной вершины до всех остальных
    D = 0 ;
 
   for (j=1; j<=2 ; j++) {        // матрица , хранящая путь из заданной вершины до всех остальных  
    G[j][1]=S;
    G[j]=0;
   }
 
 
   for (h=1 ; h<=N ;h++) {                // Алгоритм Форда-Беллмана
    i=0;
    for (j=2 ; j<=N ; j++) {
     for (k=1 ; k<=N ; k++) {
 
      if (D[k] > D[j]+m[j][k])
    D[k]=D[j]+m[j][k] ;
    i++;
 
    for (l=2 ; l<=N ; l++) {
     W[l]=D[l];                    // преобразуем для удобства массив расстояний в матрицу  (i-ая строка матрицы - массив расстояний на i-ом шаге )
     if (W[l]<W[i-1][l])           // отслеживаем улучшение пути
      G[k][2]=j ;                     // запоминаем вершину через которую проходит этот путь
    }
     }
    }
   }
 
    printf("\n");
 
  if (D[F]<MAX) {                                         // если путь существует , то ...
 
    printf("\nдлина пути от %d узла до %d узла = ",S,F);
    printf("%d \n",D[F]);                                 // выводим длину пути
 
    printf("путь между %d u %d вершинами  : ",S,F);
 
    i=1;
    Z[0]=F;
 
    while ( G[F][2] !=0 ) {                               // в массив Z записываем вершины , через которые проходит путь , в обратном порядке (от конечной к начальной вершине)
     Z=G[F][2];
     i++;
     G[F][2]=G[G[F][2]][2];
    }
     Z=S;
 
   for (j=i ; j>=0 ;j--)
    printf(" %d",Z[j]);                                   // выводим вершины , через которые проходит путь , в правильном порядке
 
  }
     else {                                               // если пути нет , то ...
      printf("\nпути нет\n\n\n");                
      return;
     }
 
return;
 
}
 
void PYTU () {                     // функция нахождения всех возможных путей между данными вершинами в графе не пеpесекающиеся по pебpам
 
   while (D[F]<MAX)  {             // пока путь существует ...
    GRAF(v);                       // вызываем функцию нахождения кратчайшего расстояния для нашего графа без учета весов рёбер (все ребра имеют вес = 1)
    for (j=0 ; j<M ; j++)
    v[Z[j+1]][Z[j]]=MAX;           // пройденные ребра удаляем (ставим вес = бесконечности )  
   }
 
  return;
}
 
 
int main () {
 
clrscr();
 
 
 char fileName[256];
   FILE *inp;
 
   printf("Введите адрес : ");
    scanf("%s", fileName);
    printf("\n");
 
    inp=fopen(fileName, "r");          // открываем файл на чтение
 
    fscanf (inp,"%d %d",&N,&M);        // Читаем из файла первую строку , содержащую число вершин N и число ребер M
 
   for ( i=1 ; i<=N ; i++)             // присваиваем элементам обоих матриц максимальные значения
    for ( j=1 ; j<=N ; j++) {
     m[j]=MAX;
     v[j]=MAX;
    }
 
   for (i=1 ;i<=M ;i++ ) {                // Читаем из файла остальные M строк ,
    fscanf(inp,"%d %d %d",&a,&b,&c);     // содержащие описание ребер (Пример строки файла :" 1 3 6 ": значит что ребро из вершины 1 в вершину 3 имеет вес 6)  
       m[a]=c;                        // Заполняем матрицу смежностей для нашего графа , учитывая вес ребра
   //  m[a]=1;                        // если граф неориентированный , то убрать метку
       v[a]=1;                        // заполняес матрицу смежностей без учёта веса рёбер (все ребра имеют вес = 1)
   }
    fclose(inp);                         // закрываем файл
 
     printf("\n");
 
   printf("Введите начало и конец пути : ");    // пример : " 1 7 " : 1 - начало , 7 - конец пути
   scanf ("%d %d",&S,&F);
 
   printf("\nВсе пути не пересекающиеся по ребрам : \n");
   PYTU();
   printf("Минимальный путь и его длина: ");
   GRAF(m);
 
 getch();
 return 0 ;
}[HTML][/HTML]
307
12 мая 2010 года
Artem_3A
863 / / 11.04.2008
код оформи в соответствии с правилами форума, а потом уже поговорим.
60K
12 мая 2010 года
Gerasym
2 / / 12.05.2010
http://sources.codenet.ru/download/3614/4a.html адрес исходника
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог