Exploring Dijkstra's Algorithm for Shortest Path in C
Explore Dijkstra's Algorithm for Shortest Path in C on our website, where we provide comprehensive guidance and practical examples. If you need help with your C assignment, this resource will equip you with valuable insights to tackle complex optimization challenges. Whether you're a student aiming to enhance your programming skills or a professional seeking solutions for real-world graph problems, our content offers the knowledge and support you need to succeed. Discover the power of Dijkstra's Algorithm and its applications in C programming.
Block 1: Main Function
```c
#include
#include
#include "structname.h"
int main()
{
// Prompt for the file to be processed and load it as a graph object
printf("Enter File Name:\n");
char filename[MAX_STR_LEN];
fgets(filename, MAX_STR_LEN, stdin);
filename[strlen(filename) - 1] = '\0';
Graph* graph = loadGraph(filename);
// Prompt for the starting node and calculate shortest paths
printf("Start Node:\n");
char line[MAX_STR_LEN];
int startingNode;
fgets(line, MAX_STR_LEN, stdin);
sscanf(line, "%d", &startingNode);
printf("Running Dijkstra on graph.\n");
printf("Input File: %s\n", filename);
printf("Start Node: %d\n", startingNode);
findShortestPath(graph, startingNode);
// Clean up and exit
freeGraph(graph);
return 0;
}
```
- This block is the main function that orchestrates the program.
- It first asks for the filename containing graph data and the starting node.
- Then, it calls the `loadGraph` function to load the graph data.
- After loading the graph, it calls the `findShortestPath` function to calculate the shortest paths.
- Finally, it releases memory and exits.
Block 2: Loading the Graph
```c
Graph* loadGraph(const char* filename)
{
// Attempt to open the file, terminate the program if the file does not exist or cannot be read.
FILE* file = fopen(filename, "r");
if (!file)
{
printf("Error: Failed to open the file.\n");
exit(1);
}
// Load the number of vertices and the connections between them
Graph* graph = (Graph*)malloc(sizeof(Graph));
fscanf(file, "%d", &graph->size);
graph->distances = (int**)malloc(sizeof(int*) * graph->size);
for (int i = 0; i < graph->size; i++)
graph->distances[i] = (int*)malloc(sizeof(int) * graph->size);
// Vertices have no connection to each other by default, hence the distance is set to 0.
int fromVertex, toVertex;
for (fromVertex = 0; fromVertex < graph->size; fromVertex++)
for (toVertex = 0; toVertex < graph->size; toVertex++)
graph->distances[fromVertex][toVertex] = 0;
// Now connect the vertices
int distance;
while (fscanf(file, "%d %d %d", &fromVertex, &toVertex, &distance) == 3)
graph->distances[fromVertex][toVertex] = distance;
return graph;
}
```
- This block defines the `loadGraph` function that reads the graph data from a file.
- It opens the file, reads the number of vertices, and creates a graph structure.
- It then connects vertices based on the input file and returns the graph.
Block 3: Freeing the Graph
```c
void freeGraph(Graph* graph)
{
for (int i = 0; i < graph->size; i++)
free(graph->distances[i]);
free(graph->distances);
free(graph);
}
```
- This block defines the `freeGraph` function, which frees memory allocated for the graph structure.
Block 4: Dijkstra's Algorithm
```c
void findShortestPath(Graph* graph, int startingNode)
{
// Make sure that the starting node exists in the graph
if (startingNode < 0 || startingNode >= graph->size)
{
printf("Error: Invalid starting node.\n");
return;
}
// Make a node object for each node to encapsulate information
Node* nodes = (Node*)malloc(sizeof(Node) * graph->size);
for (int i = 0; i < graph->size; i++)
{
nodes[i].distance = INT_MAX;
nodes[i].isVisited = FALSE;
}
// The starting node will start at distance 0
nodes[startingNode].distance = 0;
// Now we do the shortest path algorithm
while (TRUE)
{
// Find the next node to be processed, the one with the shortest distance
int nextNode = -1;
for (int node = 0; node < graph->size; node++)
{
if (!nodes[node].isVisited)
{
// Smaller distance wins; if distances are equal, the smaller node index wins
if (nextNode == -1 || nodes[node].distance < nodes[nextNode].distance)
nextNode = node;
}
}
if (nextNode == -1 || nodes[nextNode].distance == INT_MAX)
break;
nodes[nextNode].isVisited = TRUE;
// Calculate the distance from the chosen next node to adjacent ones that haven't been visited
for (int adjacentNode = 0; adjacentNode < graph->size; adjacentNode++)
{
if (!nodes[adjacentNode].isVisited && graph->distances[nextNode][adjacentNode] > 0)
{
int adjacentDistance = nodes[nextNode].distance + graph->distances[nextNode][adjacentNode];
// Always prefer to choose the shorter distance
if (adjacentDistance < nodes[adjacentNode].distance)
nodes[adjacentNode].distance = adjacentDistance;
}
}
}
// When the code reaches here, we have calculated the shortest distance from the starting node to all other nodes
printf("Shortest Distances\n");
for (int node = 0; node < graph->size; node++)
{
printf("Shortest Path From %d to %d is ", startingNode, node);
if (nodes[node].distance == INT_MAX)
printf("Infinity");
else
printf("%d", nodes[node].distance);
printf("\n");
}
free(nodes);
}
```
- This block defines the `findShortestPath` function, which implements Dijkstra's algorithm.
- It initializes data structures, such as an array of nodes, for the algorithm.
- It then performs Dijkstra's algorithm to find the shortest paths from the starting node to all other nodes.
- Finally, it prints the results, showing the shortest distances from the starting node to each node.
Block 5: Constants and Structures
```c
#define MAX_STR_LEN 100
#define TRUE 1
#define FALSE 0
typedef struct Graph Graph;
struct Graph
{
int** distances; /**< A 2 dimensional array that keeps track the connection of vertices. The indices of the array are the vertices, the content are the distances. */
int size; /**< The number of vertices in the graph */
};
typedef struct Node Node;
struct Node
{
int distance; /**< Estimated sorted distance from this node to a chosen shortest path to another node */
int isVisited; /**< Indicates if the node has been processed or not when doing Dijkstra's algorithm */
};
```
- This block defines constants and structures used in the program.
- It includes the definition of the `Graph` structure, which holds the graph data.
- It defines the `Node` structure, which is used in Dijkstra's algorithm.
- It also sets some constants for readability.
Conclusion
By following this guide, you'll gain a strong foundation in implementing Dijkstra's algorithm in C, which can be applied to various graph-related problems. Whether you're a student looking for programming homework help or a programmer seeking to enhance your knowledge, this guide will provide valuable insights and practical examples. With this newfound knowledge, you'll be better equipped to tackle real-world challenges, from optimizing transportation routes to network pathfinding. The ability to find the shortest path efficiently is a highly sought-after skill in the fields of computer science, data analysis, and beyond, making this guides a valuable resource for your journey into the world of algorithms and problem-solving.