0

If I run the following code, I get the correct output, and the path is displayed on the serial monitor. However when I run the code together with the commented out portion (in the code below) I don't get any output; even the output that is printed before this code doesn't print completely. Why is that?

I have figured it out that this happens when the dijkstra functions runs more than once. But it shouldn't happen like this.

   int *path1 = NULL;
    int no_of_nodes_1;
    dijkstra(graph, startingNode1, end1_start2, &path1, no_of_nodes_1);

    /*int *path2 = NULL;
    int no_of_nodes_2;
    dijkstra(graph, end1_start2, end2_start3, &path2, no_of_nodes_2);

    int *path3 = NULL;
    int no_of_nodes_3;
    dijkstra(graph, end2_start3, endingNode3, &path3, no_of_nodes_3);
        */
        delete graph;


    Serial.println();

    Serial.println( "PATH 1:");
    for (int k = 0; k < no_of_nodes_1; k++){
        Serial.print(path1[k]);Serial.print("..");
        }

/*
    Serial.println();
        Serial.println( "PATH 2:");
    for (int x = 0; x < no_of_nodes_2; x++){
        Serial.print(path2[x]);Serial.print("..");        
    }

    Serial.println();
    Serial.println( "PATH 3:");
    for (int y = 0; y < no_of_nodes_3; y++){
        Serial.print(path3[y]);Serial.print("..");
    }

*/

::UPDATE::

/******************************************************************************/
    void getNextNode(int node, const int& src, const int predecessor[264], int temp_path[], int& i){

        i = 1;

        if (node == src)
        {
            temp_path[i] = src;
        }

        else if (predecessor[node] == -1)
        {
                Serial.println("No path exists");
        }
        else {
            getNextNode(predecessor[node], src, predecessor, temp_path, i);
            temp_path[i] = node;
            i++;
        }

        return;
    }
/********************************************************************************/
    int* savePath(int predecessor[264], const int& src, const int& targetnode, int & numofnodes){

        int temp_path[200];
        temp_path[0] = src;
        int i;

        if (targetnode == src)
        {
            temp_path[1] = src;
        }
        else
        {
            getNextNode(targetnode, src, predecessor, temp_path, i);
        }

        numofnodes = i;
        int *path = new int[i];

        for (int k = 0; k < i; k++){
            path[k] = temp_path[k];
        }

        return path;


    }
 /****************************************************************************/   
    void dijkstra(struct Graph* graph, int src, int target, int **path, int& numofnodes)
    {
        // The main function that calulates distances of shortest paths from src to all
        // vertices. It is a O(ELogV) function

        int V = graph->V;// Get the number of vertices in graph
        int* dist = new int[V];      // dist values used to pick minimum weight edge in cut

        int predecessor[264]; //array to save nearest nodes

        // minHeap represents set E
        struct MinHeap* minHeap = createMinHeap(V);

        // Initialize min heap with all vertices. dist value of all vertices
        for (int v = 0; v < V; ++v)
        {
            dist[v] = INT_MAX;
            minHeap->array[v] = newMinHeapNode(v, dist[v]);
            minHeap->pos[v] = v;
            predecessor[v] = -1;
        }

        // Make dist value of src vertex as 0 so that it is extracted first
        minHeap->array[src] = newMinHeapNode(src, dist[src]);
        minHeap->pos[src] = src;
        dist[src] = 0;
        decreaseKey(minHeap, src, dist[src]);

        // Initially size of min heap is equal to V
        minHeap->size = V;

        // In the followin loop, min heap contains all nodes
        // whose shortest distance is not yet finalized.
        while (!isEmpty(minHeap))
        {
            // Extract the vertex with minimum distance value
            struct MinHeapNode* minHeapNode = extractMin(minHeap);
            int u = minHeapNode->v; // Store the extracted vertex number

            // Traverse through all adjacent vertices of u (the extracted
            // vertex) and update their distance values
            struct AdjListNode* pCrawl = graph->array[u].head;
            while (pCrawl != NULL)
            {
                int v = pCrawl->dest;

                // If shortest distance to v is not finalized yet, and distance to v
                // through u is less than its previously calculated distance
                if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
                    /*pCrawl->weight*/1 + dist[u] < dist[v])
                {
                    dist[v] = dist[u] + 1 /*pCrawl->weight*/; // 1 is the weight of the node
                    predecessor[v] = u;
                    // update distance value in min heap also
                    decreaseKey(minHeap, v, dist[v]);
                }
                pCrawl = pCrawl->next;
            }
        }

        delete[] dist;
        delete minHeap;
        *path = savePath(predecessor, src, target, numofnodes);
    }
  • 2
    Please provide the whole code, including the dijkstra function and the values for graph, startingNode1, end1_start2. Also there are two sections commented out. Which one are you referring to in your question? – Gerben Aug 5 '15 at 14:38
  • @Gerben I have updated the question please see it now. And I am referring to both sections together. – Muhammad Faique Shakeel Aug 8 '15 at 7:28
  • I performed a rollback to revision 3, as revision 4 deleted much of the code that was pertinent to the question. – Greenonline Jan 19 '17 at 8:18
1

You have likely run out of RAM.

You have 200 integers in the temp_path array. That equates to 400 bytes of SRAM. You also have 3 predecessor arrays each with 264 integers, which equates to 1584 bytes. These arrays combined use 1984 bytes. This is in addition to all your other variables and function calls.

The Arduino Uno only has 2KB of SRAM.

Solution:
Use an Arduino with a greater amount of SRAM.

  • ARDUINO M0/Zero - 32KB of SRAM
  • Arduino Mega - 8KB of SRAM
  • Arduino Due - 96KB of SRAM

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.