Функция BackTracking не работает должным образом

Question

Я пытаюсь решить следующий вопрос, используя BackTracking в C, но я не знаю, как продолжить отсюда ...

Вопрос:

Крис планирует путешествовать по стране с N городами. Он получит помощь от матрицы NxN, в которой ячейка (I, J) представляет собой длину дороги от города I до города J. Длина дороги от города А до города В не одинакова по сравнению с дорогой из Город B - город A. Дорога Из того же исходного города обратно (напрямую) - 0. Крис заметил, что кратчайший путь от А до В не всегда прямой между двумя городами. Вам нужно будет помочь Крису найти кратчайший путь. Напишите функцию, которая проверяет самую короткую карту с учетом матрицы NxN, в которой хранятся значения длин дорог. Примечание: N определяется как 4.

Пример:

Кратчайший путь от 0 до 1 ведет к городу 0, затем 3, затем 1, если задана следующая матрица:

0 5 2 2

1 0 1 1

1 2 0 1

1 1 2 0

Ее мой код:

int ShortestPath (int SourceCity, int DestinationCity, int Distance [][N], bool Chosen[][N])
{
    int Path=0;
    if (SourceCity==DestinationCity)
    {
        Distance[SourceCity][DestinationCity]=true;
        return 0;
    }

    for (int i=0;i<N;i++)
    {
        for (int j=0;j<N;j++)
        {
            Path += Distance[i][j];
            if (!Chosen[i][j])
            {
                Chosen[i][j] = true;
                ShortestPath(i, DestinationCity, Distance, Chosen);
            }
        }
    }
    if (Path>=Distance[SourceCity][DestinationCity])
    {
        Chosen[SourceCity,DestinationCity]=false;
        return Distance[SourceCity][DestinationCity];
    }
}

Примечание: выбранная матрица указала, выбрал я указанную c дорогу или нет (все ее начальные значения неверны)

Answer 1

Вот предлагаемое решение. Это реализация алгоритма Дейкстры, который находит кратчайший путь.

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

// number of nodes
#define N 4
// distance matrix from i to j for d[i][j]
int d[N][N] = {
    {0, 5, 2, 2},
    {1, 0, 1, 1},
    {1, 2, 0, 1},
    {1, 1, 2, 0},
};


// shortestPath stores in path the shortest path from start node to 
// final node using the distance matrix d. It returns the number of 
// nodes in the path.
int shortestPath(int d[N][N], int start, int final, int path[N]){
   // node previous to node i
   int prev[N];

   // initialize distance from node i to start as infinite
   int dist[N];
   for (int i = 0; i < N; i++)
       dist[i] = INT_MAX;
   dist[start] = 0;

   // initialize list of nodes done
   bool done[N];
   for (int i = 0; i < N; i++)
       done[i] = false;
   int nDone = 0;

   // while we haven’t done all nodes
   while (nDone < N) {
        // find not yet done node with minimal distance to start node
        int minDist = INT_MAX;
        int n; // node with minimum distance
        for (int i = 0; i < N; i++)
            if (!done[i] && dist[i] < minDist)
                minDist = dist[n = i];
        done[n] = true;
        nDone++;
        // we can stop when final node is done
        if (n == final)
            break;

        // for every node j...
        for (int j = 0; j < N; j++) {
            // if node j is not yet done, 
            // and distance from start to j through n is smaller to known
            if (!done[j] && dist[j] > dist[n] + d[n][j]) {
                // set new shortest distance
                dist[j] = dist[n] + d[n][j];
                // set node n as previous to node j
                prev[j] = n;
            }
        }
    }

    // get path [start, ..., final]
    int j = N;
    for (int i = final; i != start; i = prev[i])
        path[--j] = i;
    path[--j] = start;
    if (j == 0)
        return N;
    int n = N-j;
    for (int i = 0; i < n; i++, j++)
        path[i] = path[j];
    return n;
}

int main() {
    int path[N];
    int n = shortestPath(d, 0, 1, path);

    printf("path: %d", path[0]);
    for (int i = 1; i < n; i++)
        printf("->%d", path[i]);
    printf("\n");
    return 0;
}

Вывод

path: 0->3->1