Создание рекурсивной функции для поиска кратчайшего пути (алгоритм Джикстры) - C - PullRequest
Новая
       9

Создание рекурсивной функции для поиска кратчайшего пути (алгоритм Джикстры) - C

0 голосов
/ 19 ноября 2018

ВЫПУСК: Мне дали карту точек по всей стране, в которой мне поручено перемещаться из одного пункта назначения в другой (найти кратчайший маршрут).Я изучал алгоритм Джикстры уже несколько дней, но до сих пор не понимаю, как превратить его в работающий код.

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

КОД: 

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

#define VERT 14


int minDist(int dist[], bool sptSet[]) // a function to find the node with minimum distance value from the set of

//vertices not included in the shortest path tree.

{
    int min = INT_MAX, min_index, i = 0;

    for (; i < VERT; i++)

        if (sptSet[i] == false && dist[i] <= min) {
            min = dist[i];

            min_index = i;
        }

    return min_index;

}

void printFinal(int dist[], int n) {

    printf("Node Distance from source\n");

    for (int i = 0; i < n; i++) {
        printf("%d\n", i);
        printf("%d\n", dist[i]);
    }

}


void travelPath(int map[VERT][VERT], int start) {

    int distance[VERT];//The output array. dist[i] will hold the shortest distance from src to i

    bool sptSet[VERT];    // sptSet[i] will true if vertex i is included in shortest

    //path tree or shortest distance from src to i is finalized

    // Initialize all distances as INFINITE and stpSet[] as false

    for (int i = 0; i < VERT; i++) {

        distance[i] = INT_MAX;

        sptSet[i] = false;

    }

    // Distance of source vertex from itself is always 0

    distance[start] = 0;

    for (int count = 0; count < VERT - 1; count++) {

        int u = minDist(distance, sptSet); // Pick the minimum distance vertex from the set of vertices not

        //yet processed. u is always equal to src in first iteration.

        sptSet[u] = true; // Mark the picked vertex as processed

        for (int v = 0; v < VERT; v++) {

            // Update dist[v] only if is not in sptSet, there is an edge from

            // u to v, and total weight of path from src to v through u is

            // smaller than current value of dist[v]

            if (!sptSet[v] && map[u][v] && distance[u] != INT_MAX && distance[u] + map[u][v] < distance[v])

                distance[v] = distance[u] + map[u][v];

        }

        printFinal(distance, VERT);
    }
}


int main() {

    //points on the map with zeroes representing infinity
    int graph[VERT][VERT] = {{0,    808,  0,    0,    0,   0,    0,   0,    0,    0,    0,   0,    2060, 0},
                             {808,  0,    414,  0,    0,   0,    0,   0,    2257, 0,    0,   0,    0,    0},
                             {0,    414,  0,    1440, 0,   0,    0,   0,    0,    0,    0,   0,    0,    272},
                             {0,    0,    1440, 0,    517, 0,    0,   1614, 0,    949,  0,   0,    0,    0},
                             {0,    0,    0,    517,  0,   0,    0,   0,    0,    0,    0,   0,    1425, 0},
                             {0,    0,    0,    0,    0,   0,    0,   0,    0,    0,    0,   0,    1423, 0},
                             {0,    0,    0,    0,    0,   0,    0,   237,  811,  0,    0,   0,    0,    0},
                             {0,    0,    0,    1614, 0,   0,    237, 0,    0,    1217, 0,   0,    0,    0},
                             {0,    2257, 0,    0,    0,   0,    811, 0,    0,    0,    0,   1771, 0,    0},
                             {0,    0,    0,    949,  0,   0,    0,   1217, 0,    0,    797, 0,    0,    0},
                             {0,    0,    0,    0,    0,   0,    0,   0,    0,    0,    792, 0,    0,    0},
                             {0,    0,    0,    0,    0,   0,    0,   0,    1771, 0,    0},
                             {2060, 0,    0,    0,    948, 1423, 0,   0,    0,    0,    0,   0,    0,    0},
                             {0,    0,    272,  0,    0,   0,    0,   0,    0,    0,    0,   0,    1780, 0}};
    //passing to recursive function travelPath with the initial point
    travelPath(graph, 0);


}

Я прошу прощения, что не над чем работать, вот в чем проблема, я непонять, как элегантно пройти по карте, используя рекурсию ...

Спасибо за любые рекомендации, которые вы можете предоставить!

Вот карта расстояний для справки enter image description here

ЖЕЛАЕМЫЙ ВЫХОД: 

Which two cities would you like to find the shortest routes between?
New York
San Francisco


New York --> Washington D.C.
Washington D.C. --> Milwaukee
Milwaukee --> San Francisco
The end!

РЕДАКТИРОВАТЬ: добавлена ​​справочная карта и дополнительный код.

...