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);
}
