THIS IS MY CODE HELP ME ACHIEVE POINTS OUTLINED BELOW : #include #include #include #include #include "graph.h" #include "dijkstra.h" #define INFINITY DBL_MAX /* find shortest paths between source node id and all other nodes in graph. */ /* upon success, returns an array containing a table of shortest paths. */ /* return NULL if *graph is uninitialised or an error occurs. */ /* each entry of the table array should be a Path */ /* structure containing the path information for the shortest path between */ /* the source node and every node in the graph. If no path exists to a */ /* particular desination node, then next should be set to -1 and weight */ /* to DBL_MAX in the Path structure for this node */ Path *dijkstra(Graph *graph, int id, int *pnEntries) { int n; int i, j; int* nv = get_vertices(graph, &n); int *S = malloc(n * sizeof(int)); double *D = malloc(n * sizeof(double)); int *R = malloc(n * sizeof(int)); Path *table = malloc(n * sizeof(Path)); /* check if graph and starting node are valid */ if (graph == NULL || id < 0 || id >= n) { *pnEntries = 0; return NULL; } /* initialize S to contain all the networks (vertices) except the source node */ for (i = 0, j = 0; i < n; i++) { if (i != id) { S[j++] = i; } } /* initialize D with the weights of the edges from the source node, or infinity if no edge exists */ for (i = 0; i < n; i++) { Edge *edge = get_edge(graph, id, i); if (edge != NULL) { D[i] = edge_weight(edge); R[i] = id; } else { D[i] = INFINITY; R[i] = 0; } } /* repeatedly follow the remaining rules of Dijkstra's algorithm, updating the values in D and R until S is empty */ while (n > 1) { /* find the vertex in S with the smallest value in D */ int u = S[0]; double min = D[u]; for (i = 1; i < n - 1; i++) { if (D[S[i]] < min) { u = S[i]; min = D[u]; } } /* remove vertex u from S */ for (i = 0; i < n - 1; i++) { if (S[i] == u) { S[i] = S[n - 2]; break; } } n--; /* update the values in D and R for the remaining vertices in S */ for (i = 0; i < n - 1; i++) { int v = S[i]; Edge *edge = get_edge(graph, u, v); if (edge != NULL && D[v] > D[u] + edge_weight(edge)) { D[v] = D[u] + edge_weight(edge); R[v] = u; } } } /* create the routing table to be returned */ for (i = 0; i < n; i++) { table[i].next_hop = R[i]; table[i].weight = D[i]; } /* free unused memory and set *pnEntries to the correct value */ free(S); free(D); free(R); *pnEntries = n; free(nv); return table; }
THIS IS MY CODE HELP ME ACHIEVE POINTS OUTLINED BELOW :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include "graph.h"
#include "dijkstra.h"
#define INFINITY DBL_MAX
/* find shortest paths between source node id and all other nodes in graph. */
/* upon success, returns an array containing a table of shortest paths. */
/* return NULL if *graph is uninitialised or an error occurs. */
/* each entry of the table array should be a Path */
/* structure containing the path information for the shortest path between */
/* the source node and every node in the graph. If no path exists to a */
/* particular desination node, then next should be set to -1 and weight */
/* to DBL_MAX in the Path structure for this node */
Path *dijkstra(Graph *graph, int id, int *pnEntries)
{
int n;
int i, j;
int* nv = get_vertices(graph, &n);
int *S = malloc(n * sizeof(int));
double *D = malloc(n * sizeof(double));
int *R = malloc(n * sizeof(int));
Path *table = malloc(n * sizeof(Path));
/* check if graph and starting node are valid */
if (graph == NULL || id < 0 || id >= n)
{
*pnEntries = 0;
return NULL;
}
/* initialize S to contain all the networks (vertices) except the source node */
for (i = 0, j = 0; i < n; i++)
{
if (i != id)
{
S[j++] = i;
}
}
/* initialize D with the weights of the edges from the source node, or infinity if no edge exists */
for (i = 0; i < n; i++)
{
Edge *edge = get_edge(graph, id, i);
if (edge != NULL)
{
D[i] = edge_weight(edge);
R[i] = id;
}
else
{
D[i] = INFINITY;
R[i] = 0;
}
}
/* repeatedly follow the remaining rules of Dijkstra's
while (n > 1)
{
/* find the vertex in S with the smallest value in D */
int u = S[0];
double min = D[u];
for (i = 1; i < n - 1; i++)
{
if (D[S[i]] < min)
{
u = S[i];
min = D[u];
}
}
/* remove vertex u from S */
for (i = 0; i < n - 1; i++)
{
if (S[i] == u)
{
S[i] = S[n - 2];
break;
}
}
n--;
/* update the values in D and R for the remaining vertices in S */
for (i = 0; i < n - 1; i++)
{
int v = S[i];
Edge *edge = get_edge(graph, u, v);
if (edge != NULL && D[v] > D[u] + edge_weight(edge))
{
D[v] = D[u] + edge_weight(edge);
R[v] = u;
}
}
}
/* create the routing table to be returned */
for (i = 0; i < n; i++)
{
table[i].next_hop = R[i];
table[i].weight = D[i];
}
/* free unused memory and set *pnEntries to the correct value */
free(S);
free(D);
free(R);
*pnEntries = n;
free(nv);
return table;
}
Step by step
Solved in 4 steps with 4 images
