Решение задачи на вычисление количества бензина для проезда между несколькими городами, страница 3

поиск кратчайшего пути от первой вершины к последней по алгоритму Дейкстры. Функция возвращает длину кратчайшего пути или 10000, если проехать не возможно ( проверка можно ли проехать осуществляется в функции main).

- прототип функции:

int Poisk (int **C, int N)

- параметры:

C- (входной паремтр) матрица смежности;

N- (входной параметр) количество городов/ размерность матрицы C

5.2. Структура программы по управлению

 

6. Текст программы на языке Си

Main.cpp

#include <stdio.h>

#include <conio.h>

#include <locale.h>

int** Vvod(int N, FILE *fp);

int Poisk(int **С,int N);

void main()

{

     setlocale(LC_CTYPE, "Russian");// подключение русского языка

     FILE *fp, *fp1;

     int N,i,rez;//N-количество вершин,M- количество дорог

     fp=fopen("Input.txt","r");

     fp1=fopen("Path.txt","w");

     fscanf (fp," %d", &N);// читаем количество городов из файла "input.txt"

     if (N==1) fprintf(fp1,"-1");//если город 1, то вывести -1

     else

     {

          int **C=new int*[N];

          for(i=0;i<N;i++)

               C[i]=new int[N];

          C=Vvod(N, fp);// вызов подпрограммы Ввод

          rez=Poisk(C,N);//вызов подпрограммы Поиск

          if (rez!=10000) fprintf(fp1,"%d",rez);//если доехать можно, вывести путь

          else fprintf(fp1,"-1");//иначе, вывести -1

          fclose(fp1);

          fclose(fp);

     }

     printf("Программа выполнилась, смотри в \"Path.txt\"");

     getch();

}

/*----------------------------------------------------------------------------*/

/*Попдпрограмма Ввод создает матрицу смежности*/

int** Vvod(int N, FILE *fp)

{

     int i,j,M,k,p;//M- количество дорог

     int **A=new int*[N];

     for(i=0;i<N;i++)

          A[i]=new int[N];//создали массив A[N][N]

     int *B=new int[N];// создали массив B[N]

     for(i=0;i<N;i++)

     for(j=0;j<N;j++)

          A[i][j]=10000;//элементам массива A присваиваем бесконечно большие числа (в данном случае 10000)

     for(i=0;i<N;i++)

          fscanf(fp,"%d",&B[i]);// в массив B занесли стоимость бензина в каждом городе

     fscanf(fp,"%d", &M);//сканируем кол-во дорог

for(i=0;i<M;i++)         //Создаем

     {                        //мат-

          fscanf(fp,"%d", &k);//ри-

          fscanf(fp,"%d", &p);//цу

          A[k-1][p-1]=B[k-1];//смеж-

          A[p-1][k-1]=B[p-1];//ности

     }

     return A;

}

/*----------------------------------------------------------------------------*/

//Подпрограмма Поиск находит кратчайший путь из первого города в последний

int Poisk(int **C,int N)

{

     int *D=new int[N];// создали массив D[N]

     int i,j,e=0;

     if (C[0][N-1]!=10000) return C[0][N-1];  //Если 1-ый и N-ый город соеденены прямой дорогой,

                                                   //то стоимость проезда равна стоимости бензина в первом городе

     else

     {

          D[0]=0;//первый эл-т массива D приравниваем 0

          for(j=1;j<N;j++)

               D[j]=C[0][j];//всем элементам массива D, кроме превого, приравниваем соответствующие элементы первой строки массива A

          /*Если элемент следующей строки массива A не равен нулю, то мы сравниваем j-ый элемент массива D с суммой соответствующего

          i-ого j-ого элемента массива A и i-ого элемента массива D.

          i-ый элемент массива D, это минимальная стоимость проезда (на данный момент) до города (i-ого) из которого мы в данный

          момент рассматриваем путь.