минимальное нахождение пути с использованием обратного отслеживания

Question

Я пытаюсь решить свою домашнюю работу и придерживаюсь ее, надеюсь, кто-то протянет руку.

это выглядит так: учитывая матрицу NxN, каждая ячейка [i, j] описывает расстояние между два города: расстояние от i до j. мы пытаемся найти кратчайший маршрут между двумя заданными городами - так, чтобы мы могли найти более короткие маршруты по другим городам: пример: от города 1 до 3: мы можем найти кратчайший маршрут, перейдя от 1 до 2 до 0 до 3. Вот пример:

Пожалуйста, введите дорожную матрицу:

0 5 2 2

1 0 1 1

1 2 0 1

1 1 2 0

Пожалуйста, введите исходный город:

0

Пожалуйста, введите город назначения:

1

Кратчайший путь это:

0 3 1

Это то, что я до сих пор:

/*-------------------------------------------------------------------------
Include files:
--------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>



/*=========================================================================
  Constants and definitions:
==========================================================================*/

/* put your #defines and typedefs here*/

#define N 4

void PrintWelcomeMessage();
void PrintSourceCityMessage();
void PrintDestinationCityMessage();
void PrintSpace();
void PrintNumber(int num);
void BestRoute(int Roads[N][N] , int start , int destination);


/*-------------------------------------------------------------------------
  The main program. (describe what your program does here)
 -------------------------------------------------------------------------*/
int main()
{
    int start=0, destination=0, dest=0;
    PrintWelcomeMessage();
    int Roads[N][N]={{0}};
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            scanf("%d", &dest);
            Roads[i][j]=dest;
        }
    }
    PrintSourceCityMessage();
    scanf("%d",&start);
    PrintDestinationCityMessage();
    scanf("%d",&destination);
    printf("The shortest path is:\n");
    BestRoute(Roads, start, destination);

 return 0;
}




void BestRoute(int Roads[N][N] , int start , int destination, int path[N])
{
  if(start==destination) 
  {
      printf("%d ", start);
      return 0;
  }
  int min=Roads[start][destination];
  int current=0, route=0, chosenR=-1;

  for(int i=0; i<N; i++)
  {
    if(i==start)
        continue;
    current=Roads[start][i];
    Roads[start][i] =-1;
    if(Roads[i][start]==-1)
        continue;
    route=BestRoute(Roads, i, destination);
    if (route+current<min)
    {
        min=route+current;
        chosenR=i;
    }
  }
  if (chosenR!=-1)
    printf("%d ", chosenR);
}

void PrintWelcomeMessage()
{
    printf("Please enter road matrix:\n");
}

void PrintSourceCityMessage()
{
    printf("Please enter source city:\n");
}

void PrintDestinationCityMessage()
{
    printf("Please enter destination city:\n");
}

void PrintSpace() 
{
    printf(" ");
}

void PrintNumber(int num)
{
    printf("%d", num);
}