Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.12.2010, 01:39   #1
rubakKa
Пользователь
 
Регистрация: 30.11.2010
Сообщений: 29
По умолчанию длина пути между двумя вершинами в графе

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.
Входные данные
Во входном файле INPUT.TXT записано сначала число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Затем записаны номера двух вершин – начальной и конечной.
Выходные данные
В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число – 1.


Пример:
Файл ввода
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5

Файл вывода
3

Решать не обязательно.. Просто объясните алгоритм..
rubakKa вне форума Ответить с цитированием
Старый 19.12.2010, 10:42   #2
casekey
Пользователь
 
Регистрация: 03.11.2010
Сообщений: 95
По умолчанию

нужно использовать алгоритм Уоршалла для нахождения матрицы минимальных длин путей.

предположим, что A - это матрица смежности графа. Заменим все нулевые элементы A на "бесконечность" или на некоторое "очень большое число", которое обозначим через B.

в коде это примерно так:

Код:
const int B = 1000;
//Ввод матрицы смежностей заданного графа и ее "исправление"
 WriteLn ('Вводите элементы матрицы смежностей по стро-кам:');
   for (int i = 0; i<MaxNodes; i++)
       for (int j = 0; j<MaxNodes; j++)
            {
             Adj[i][j] = rand(2); // вообщем генерация матрицы смежности
             If (Adj[i][j]==0)  C[i][j] = B 
             else C[i][j] = Adj[i][j];
            }
// Вычисление матрицы минимальных длин путей
   for (int k = 0; k< MaxNodes; k++)
       for (int i = 0; i< MaxNodes; i++)
           for (int j = 0; j< MaxNodes; j++)
               If (C[i][j]>(C[i][k]+C[k][j]))
                   C[i][j] = C[i][k]+C[k][j];
Где Adj - матрица смежности. А C - матрица минимальных длин путей, в которой хранятся минимальные пути из i в j вершины
casekey вне форума Ответить с цитированием
Старый 19.12.2010, 10:55   #3
rubakKa
Пользователь
 
Регистрация: 30.11.2010
Сообщений: 29
По умолчанию

А что такое MaxNodes?
rubakKa вне форума Ответить с цитированием
Старый 19.12.2010, 10:59   #4
rubakKa
Пользователь
 
Регистрация: 30.11.2010
Сообщений: 29
По умолчанию

А если через волновой алгоритм?:
Код:
#include <stdio.h>
main(){
       FILE *in,*out;
       in=fopen("input.txt","r");
       out=fopen("output.txt","w");
       char N[101][101];
       int i,n,j,nn,nm,m;
       m=0; // длина пути
       fscanf(in,"%d",&n); // количество вершин
       for(i=0;i<n;i++){
       for(j=0;j<n;j++){
       fscanf(in,"%d",&N[i][j]);
       }
       }
       for(i=0;i<n;i++)
       fscanf(in,"%d %d",&nn,&nm); //nn - начальная, nm - конечная вершина
       for(i=nn;i<=nm;i++){
       for(j=nn;j<=nm;j++){
                  if(N[i][j]==1) // если от nn до nm встречается единица, то m увеличить на единицу
                  m++;
                  else m=1; // если нет то m=1 (по условию)
                  }
                  }
               
                            
       fprintf(out,"%d",m); // вывести m
       fclose(in);
       fclose(out);
       }
Но результат 1 т.е. пути не существует.. В чем ошибка?
rubakKa вне форума Ответить с цитированием
Старый 19.12.2010, 11:15   #5
rubakKa
Пользователь
 
Регистрация: 30.11.2010
Сообщений: 29
По умолчанию

Цитата:
нужно использовать алгоритм Уоршалла для нахождения матрицы минимальных длин путей.
И зачем мне матрица? Мне нужно найти минимальный путь. Данный алгоритм тут не подходит..
rubakKa вне форума Ответить с цитированием
Старый 19.12.2010, 17:54   #6
casekey
Пользователь
 
Регистрация: 03.11.2010
Сообщений: 95
По умолчанию

как не подходит - очень даже подходит. С помощью этой матрицы уже можно определить пути из любой вершины в любую, например если матрица такая

1 2 0
3 4 1
2 0 2

то минимальный путь из одной вершины в другую - это 1 (из 2 в 3) - это если не считать петли
casekey вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Заданная длина пути Ubersetzer Помощь студентам 0 16.11.2010 16:44
Кратчайший путь между двум вершинами Gapro Общие вопросы C/C++ 4 04.11.2010 20:24
кратчайшие расстояния между вершинами pum-pum-pum Помощь студентам 1 07.01.2010 11:30
Кратчайшее расстояние между всеми вершинами ooooch Помощь студентам 5 15.11.2009 15:36