Question & Answer: Please correct the errors in both the .c and .h files…..

Please correct the errors in both the .c and .h files

Both files are codded in C

Include COMMENTS on what you modified if it is not a compile error

Implement the TODO to print the shortest path in the Dijikstra’s Algorithm. The TODO is in a comment down below

***Down below is the .C file of the code***

//Dijikstra.c

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include “Dijikstra.h”

//#define INFINITY 999999

//#define UNDEFINED -1

//#define MAXSIZE 100

int main(int argc, char *argv[])

{

Graph g;

g.verticesLL_head = NULL;

g.edgesLL_head = NULL;

//populate vertices

int i;

for(i = 1; i <= 6; i++) {

Vertex * v = (Vertex *)malloc(sizeof(Vertex));

v->vertexId = i;

v->distance = INFINITY;

v->adjacent = false;

v->previousVertexId = UNDEFINED;

insertVertex(&g.verticesLL_head, v);

}

//populate edges

//Edge v1_v2 = { getVertex(g.verticesLL_head, 1), getVertex(g.verticesLL_head, 2), 2 };

Edge v1_v2 = { getVertex(g.verticesLL_head, 1), getVertex(g.verticesLL_head, 2), 2 };

insertEdge(&g.edgesLL_head, &v1_v2);

Edge v1_v3 = {getVertex(g.verticesLL_head, 1), getVertex(g.verticesLL_head, 3), 4};

insertEdge(&g.edgesLL_head, &v1_v3);

Edge v2_v3 = {getVertex(g.verticesLL_head, 2), getVertex(g.verticesLL_head, 3), 1};

insertEdge(&g.edgesLL_head, &v2_v3);

Edge v2_v4 = {getVertex(g.verticesLL_head, 2), getVertex(g.verticesLL_head, 4), 4};

insertEdge(&g.edgesLL_head, &v2_v4);

Edge v2_v5 = {getVertex(g.verticesLL_head, 2), getVertex(g.verticesLL_head, 5), 2};

insertEdge(&g.edgesLL_head, &v2_v5);

Edge v3_v5 = {getVertex(g.verticesLL_head, 3), getVertex(g.verticesLL_head, 5), 3};

insertEdge(&g.edgesLL_head, &v3_v5);

Edge v5_v4 = {getVertex(g.verticesLL_head, 5), getVertex(g.verticesLL_head, 4), 3};

insertEdge(&g.edgesLL_head, &v5_v4);

Edge v5_v6 = {getVertex(g.verticesLL_head, 5), getVertex(g.verticesLL_head, 6), 2};

insertEdge(&g.edgesLL_head, &v5_v6);

Edge v4_v6 = {getVertex(g.verticesLL_head, 4), getVertex(g.verticesLL_head, 6), 2};

insertEdge(&g.edgesLL_head, &v4_v6);

Vertex * source = getVertex(g.verticesLL_head, 1);

Vertex * target = getVertex(g.verticesLL_head, 6);

Vertex_LL * shortestPath = (Vertex_LL *)Dijikstra(g, source, target);

//TODO: PRINT shortestPath and distance from source to target

return EXIT_SUCCESSS;

}

//accepts a Graph = <{Vertex}, {Edge}> and a source and target vertex

//returns a linked-list of vertices which constitutes the shorted path from source —> target

//the path LL is ordered {source, v2, v3, …. target}, each vertex in the path contains its

//shortest distance from the source

Vertex_LL * Dijikstra(Graph graph, Vertex * source, Vertex * target) {

//set Q now exists implicitly in Vertex, i.e. bool adjacent, which is set to false when it is removed

//initially set to true, meaning that it is an adhacent vertex candidate

// INITIALIZE EACH VERTEX IN THE GRAPH

// for each vertex v in Graph: // Initialization

// dist[v] <- INFINITY // Unknown distance from source to v

// prev[v] <- UNDEFINED // Previous node in optimal path from source

// add v to Q // All nodes initially in Q (unvisited nodes)

// dist[source] <- 0 // Distance from source to source

//set source vertex distance to zero(0)

source->distance = 0;

// PSEUDO CODE FOR WHAT FOLLOWS BELOW

// while Q is not empty:

// u ↠vertex in Q with min dist[u] // Node with the least distance will be selected first

// remove u from Q

//

// for each neighbor v of u: // where v is still in Q.

// alt ↠dist[u] + length(u, v)

// if alt < dist[v]: // A shorter path to v has been found

// dist[v] ↠alt

// prev[v] ↠u

//

// return dist[], prev[] //now return VERTEX_LL* shortest path

//while some vertex is a adjacent candidate

while(adjacentVerticesExist(graph)) {

// vertex with min distance from source

Vertex * u = findMin(graph.verticesLL_head);

//remove vertex ‘u’ from set Q

u->adjacent = false;

//get neighbors of u

Vertex_LL * neighbors = getNeighbors(graph.edgesLL_head, u->vertexId);

//for every neighbor

while(neighbors != NULL) {

Vertex * v = neighbors->vertex;

Edge * e = getEdge(graph.edgesLL_head, u, v);

int alt = neighbors->vertex->distance + e->weight;

if(alt < v->distance) {

v->distance = alt;

v->previousVertexId = u->vertexId;

}

} // end inner while

} // end outer while

//push target onto Stack

push(target->vertexId);

int prevId = (*target).previousVertexId;

while(prevId != UNDEFINED){

push(prevId);

Vertex * v = getVertex(graph.verticesLL_head, prevId);

prevId = v->previousVertexId;

}

//push source

push(source->vertexId);

//construct path from source –> target

Vertex_LL * path = NULL;

while(!isEmptyStack()) {

int vertexId = pop();

Vertex * v = getVertex(graph.verticesLL_head, vertexId);

insertVertex(&path, v);

}

return path; //shortest path from source to target

} // end function

//set of vertices that have not been removed as adjacent vertex candidates exist

bool adjacentVertexExist(Graph g) {

Vertex_LL * ptr = g.verticesLL_head;

while(ptr != NULL) {

if(ptr->vertex->adjacent == true)

return false;

else

ptr = ptr->next;

}

return true;

}

//inserts vertex at the start of LL

void insertVertex(Vertex_LL **head, Vertex * v) {

Vertex_LL * newLL_node = (Vertex_LL *)malloc(sizeof(Vertex_LL)); //(Vertex_LL *) casts memory from malloc

newLL_node->vertex = *v;

newLL_node->next = *head;

*head = newLL_node;

}

//inserts vertex at the start of LL

void insertEdge(Edge_LL **head, Edge * e) {

Edge_LL * newLL_node = (Edge_LL *)malloc(sizeof(Edge_LL)); //(Edge_LL *) casts memory from malloc

newLL_node->edge = e;

newLL_node->next = *head;

*head = newLL_node;

}

//given vertex pair (u,v) return its edge if it exists

//other wise return NULL

Edge * getEdge(Edge_LL * head, Vertex * u, Vertex *v) {

Edge_LL * ptr = head;

while(ptr != NULL) {

if((ptr->edge.u == u && ptr->edge.v == v) || (ptr->edge.u == v && ptr->edge.v == u)) //bidirectional edge

return ptr->edge;

else

ptr = ptr->next;

}

return NULL;

}// end getEdge

//returns a LL list of all candidate neighbors of vertexId

Vertex_LL * getNeighbors(Edge_LL * head, int vertexId) {

Edge_LL * edgeLL_ptr = head;

Vertex_LL * vertex_head;

while(edgeLL_ptr != NULL) {

if(edgeLL_ptr->edge->u->vertexId == vertexId && edgeLL_ptr->edge->u->adjacent != false)

insertVertex(&vertex_head, edgeLL_ptr->edge->u);

edgeLL_ptr = edgeLL_ptr->next;

}

return vertex_head;

} // end getNeighbors

//find and return a pointer to Vertex in LL with vertexId

//returns null if no such vertexId found

Vertex * getVertex(Vertex_LL * head, int vertexId) {

Vertex_LL * ptr = head;

while(ptr != NULL) {

if(ptr->vertex.vertexId == vertexId)

break;

else

ptr = ptr->next;

}

return ptr;

} // end getVertex

//find vertex with min distance to source

Vertex * findMin(Vertex_LL * head) {

Vertex_LL * ptr = head;

int min = INFINITY;

Vertex * minVertex = NULL;

while(ptr != NULL) {

if(ptr->vertex.distance < min) {

min = ptr->vertex.distance;

minVertex = ptr->vertex;

}

ptr = ptr->next;

}

return minVertex;

} // end findMin

int stack[MAXSIZE];

int top = -1;

bool isEmptyStack() {

if(top == -1)

return true;

else

return false;

} // end isEmpty

bool isFullStack() {

if(top == MAXSIZE -1)

return true;

else

return false;

} // end isFull

int pop() {

int vertexId = -1;

if(!isEmptyStack()) {

vertexId = stack[top];

top = top – 1;

}else {

printf(“Could not retrieve data, Stack is empty.n”);

}

return vertexId;

} // end pop

void push(int vertexId) {

if(!isFullStack()) {

top = top + 1;

printf(“push vertex with Id %d, top is %dn”, vertexId, top);

stack[top] = vertexId;

//printf(“push stack[top] = data, top is %dn”, top);

}else {

printf(“Could not insert vertex, Stack is full, top is %d.n”, top);

}

} // end push

***Down below is the .h file of the code***

//Dijikstra.h

#include <stdlib.h>

#include <stdbool.h>

#define INFINITY 999999

#define UNDEFINED -1

#define MAXSIZE 10;

#define EXIT_SUCCESSS 0

/**** typedefs ****/

/*

typedef struct

{

int vertexId; // element of {1, 2, 3, … N}, a unique id assigned to each vertex

double Latitude;

double Longitude;

int stopNumber;

char * streetAddress; //also uniquely identifies a vertex location

int distance = INFINITY; //the distance from the source/start, initially set to a large number

bool adjacent = true;

int previousVertexId = UNDEFINED;

} Vertex;

*/

typedef struct

{

int vertexId; // element of {1, 2, 3, … N}, a unique id assigned to each vertex

int distance; //the distance from the source/start, initially set to a large number

bool adjacent;

int previousVertexId;

} Vertex;

typedef struct

{

Vertex * u; // and edge is any pair of Vertices (u, v) or (v, u)

Vertex * v;

double weight;

} Edge;

// an element in a linked-list of vertices

typedef struct Vertex_LL

{

Vertex * vertex;

struct Vertex_LL * next;

} Vertex_LL;

typedef struct // an element in a linked-list of edges

{

Edge * edge;

struct Edge_LL * next;

} Edge_LL;

typedef struct

{

Vertex_LL * verticesLL_head; //linked-list of vertices

Edge_LL * edgesLL_head; //linked-list of edges

} Graph;

//C functions can be written to obtain all adjacent or neighboring vertices.

//accepts a Graph = <{Vertex}, {Edge}> and a source and target vertex

//returns a linked-list of vertices which constitutes the shorted path from source —> target

//the path LL is ordered {source, v2, v3, …. target}, each vertex in the path contains its

//shortest distance from the source

Vertex_LL * Dijikstra(Graph graph, Vertex * source, Vertex * target);

//returns an array of Vertex, e.g. Vertex adjacent[ ] , that each share an edge with ‘v’.

//returns NULL is there are no adjacent edges .

Vertex * getAdjacentVertices(Graph graph, Vertex *v);

//find and return a pointer to Vertex in LL with vertexId

//returns null if no such vertexId found

Vertex * getVertex(Vertex_LL *head, int vertexId);

// vertices that have not been removed as adjacent vertex candidates exit

bool adjacentVertexExist(Graph g);

//USING A LINKED-LIST for Vertices

//inserts vertex at the start of LL

void insertVertex(Vertex_LL **head, Vertex * v);

bool VertexLLisEmpty(Vertex_LL * head);

//returns a LL list of all candidate neighbors of vertexId

Vertex_LL * getNeighbors(Edge_LL * head, int vertexId);

//find vertex with min distance to source

Vertex * findMin(Vertex_LL * head);

//USING A LINKED-LIST for Edges

void insertEdge(Edge_LL **head, Edge *edge);

bool EdgeLLisEmpty(Edge_LL * head);

//given vertex pair (u,v) return its edge if it exists

//other wise return NULL

Edge * getEdge(Edge_LL * head, Vertex * u, Vertex *v);

//STACK

bool isEmptyStack();

bool isFullStack();

//pops vertexId on top of stack

int pop();

void push(int vertexId);

***Down below is a sample program that helps find the shortest path in a Dijikstra problem***

/* Dijkstra’s Algorithm in C */
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<string.h>
#include<math.h>
#define IN 99
#define N 6
int dijkstra(int cost[][N], int source, int target);
int dijsktra(int cost[][N],int source,int target);
int main()

{
int cost[N][N],i,j,w,ch,co;
int source, target,x,y;
printf(“t The Shortest Path Algorithm ( DIJKSTRA’S ALGORITHM in C nn”);
for(i=1;i< N;i++)
for(j=1;j< N;j++)
cost[i][j] = IN;
for(x=1;x< N;x++)
{
for(y=x+1;y< N;y++)
{
printf(“Enter the weight of the path between nodes %d and %d: “,x,y);
scanf(“%d”,&w);
cost [x][y] = cost[y][x] = w;
}
printf(“n”);
}
printf(“nEnter the source:”);
scanf(“%d”, &source);
printf(“nEnter the target”);
scanf(“%d”, &target);
co = dijsktra(cost,source,target);
printf(“nThe Shortest Path: %d”,co);
}
int dijsktra(int cost[][N],int source,int target)
{
int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;
char path[N];
for(i=1;i< N;i++)
{
dist[i] = IN;
prev[i] = -1;
}
start = source;
selected[start]=1;
dist[start] = 0;
while(selected[target] ==0)
{
min = IN;
m = 0;
for(i=1;i< N;i++)
{
d = dist[start] +cost[start][i];
if(d< dist[i]&&selected[i]==0)
{
dist[i] = d;
prev[i] = start;
}
if(min>dist[i] && selected[i]==0)
{
min = dist[i];
m = i;
}
}
start = m;
selected[start] = 1;
}
start = target;
j = 0;
while(start != -1)
{
path[j++] = start+65;
start = prev[start];
}
path[j]=’’;
strrev(path);
printf(“%s”, path);
return dist[target];
}