CODEWITHSUNDEEP
cdijkstra
lajtmaN
lajtmaN

Reputation: 465

Implement Dijkstra's algorithm in C problems

We've been doing a project with a robot driving in a room, and when we activate it, it returns to a choosen destination. Our task is to find the shortest path to that destination.

We've been coding in C, and trying to use Dijkstra's algorithm, but we are kinda stuck right now. We dont get the shortest route. The first position in weights is the start coordinate, and end is the last.

double dijkstras(double weights[MAX_ARRAY_SIZE][MAX_ARRAY_SIZE], char output[], int     *output_number_of_waypoints, int number_of_waypoints){ 

double route_length[number_of_waypoints];
int shortest_route_via[number_of_waypoints];

int i, current_pos;
double distance;
for (i = 0; i < number_of_waypoints; i++) {
    route_length[i] = 0;
    shortest_route_via[i] = -1;
}

int start = 0;                   /* first index in array */
int end = number_of_waypoints-1; /* last index in array */

for (current_pos = start; current_pos <= end; current_pos++) {
    for (i = 0; i < number_of_waypoints; i++) {
        if (weights[current_pos][i] > 0) {
            distance = route_length[current_pos] + weights[current_pos][i];
            if (distance < route_length[i] || shortest_route_via[i] == -1) {
                printf("shortest_route_via[%d] = current_pos = %d, length was %lf, shorted to %lf\n", i, current_pos, route_length[i], distance); /* debugging info */
                route_length[i] = distance;
                shortest_route_via[i] = current_pos;
            }
        }
    }
}
current_pos = end;
i = 0;
char route[number_of_waypoints+1];
while (current_pos != start && i < number_of_waypoints) {
    route[i] = current_pos;
    printf("currentpos = %d\n", current_pos); /* Debugging info - shortest path */
    current_pos = shortest_route_via[current_pos];
    i++;
}
route[i] = '\0';

return route_length[end];

}

We want to get a array - shortest_route_via, which contains the shortest route via index - for example shortest_route_via[index] = waypoint. Route_length contains the cost to travel to the index, for example route_length[index] = 100, means it costs 100 to travel to index.

Hope some1 out there can see what we are missing.

Upvotes: 3

Views: 2054

Answers (1)

Origin
Origin

Reputation: 2017

If I interpret your code correctly, you're not really doing Dijkstra.

Dijkstra starts at a root node and then looks at all neighbors it can reach. The distance from the root to all the neighbors is then tentatively set. In the next iterations, the closest among the tentatively set nodes is made permanent and its neighbors are tentatively set.

Your code doesn't select the closest node. You just iterate over all nodes in the order of their id's by incrementing current_pos. Unless the shortest path is strictly incremental in node order (the indices only increase like 1->4->10->14->...), you won't get the guaranteed shortest path.

Upvotes: 3

Related Questions