В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами - C (СИ)

Узнай цену своей работы

Формулировка задачи:

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами. Входные данные Во входном файле INPUT.TXT записано сначала число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Затем записаны номера двух вершин – начальной и конечной. Выходные данные В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число – 1. У меня получается так:
#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.. В чем ошибка? P.S. прошу прощения за название темы

Решение задачи: «В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами»

textual
Листинг программы
if(N[i][j]==1)

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 3.8 из 5
Похожие ответы