Skip to content

Instantly share code, notes, and snippets.

@oriapp

oriapp/dijkstra_algo.c

Created February 3, 2025 16:41
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save oriapp/9e42dc87154c6e6626dfb6a3b8331598 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save oriapp/9e42dc87154c6e6626dfb6a3b8331598 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
dijkstra_algo.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#ifdef _WIN32
#include <windows.h>
#else
#include <unistd.h>
#endif
#define ROWS 10
#define COLS 10
#define INF 1000000000
// A structure to represent a cell (point) in the grid.
typedef struct {
int x;
int y;
} Point;
// Our grid: S = start, E = end, '#' = obstacle, ' ' = free cell.
char grid[ROWS][COLS + 1] = {
"S ",
" ### ## ",
" # ",
" # ## ",
" #### ",
" ",
" ## ## ",
" ## ",
" ## ",
" E"
};
// Function prototypes
void clearScreen(void);
void sleepMilliseconds(int ms);
void printVisualization(const int visited[ROWS][COLS], const int dist[ROWS][COLS],
Point current, Point start, Point end);
void runDijkstra(void);
int main(void) {
runDijkstra();
return 0;
}
// Clears the terminal screen.
void clearScreen(void) {
#ifdef _WIN32
system("cls");
#else
system("clear");
#endif
}
// Sleeps for the specified number of milliseconds.
void sleepMilliseconds(int ms) {
#ifdef _WIN32
Sleep(ms);
#else
usleep(ms * (1000 / 3));
#endif
}
// Prints the grid with a visualization overlay.
// - '@' indicates the current cell being processed.
// - 'S' and 'E' mark the start and end.
// - '#' are obstacles.
// - '.' marks visited cells.
// - '+' marks cells that have been discovered (tentative distance updated).
// - ' ' marks unreached cells.
void printVisualization(const int visited[ROWS][COLS], const int dist[ROWS][COLS],
Point current, Point start, Point end) {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (i == current.x && j == current.y) {
printf("@");
} else if (i == start.x && j == start.y) {
printf("S");
} else if (i == end.x && j == end.y) {
printf("E");
} else if (grid[i][j] == '#') {
printf("#");
} else if (visited[i][j]) {
printf(".");
} else if (dist[i][j] < INF) {
printf("+");
} else {
printf(" ");
}
}
printf("\n");
}
}
// Runs the Dijkstra's algorithm on our grid and visualizes each step.
void runDijkstra(void) {
int dist[ROWS][COLS];
int visited[ROWS][COLS];
Point prev[ROWS][COLS]; // To reconstruct the shortest path.
// Initialization: set distances to INF, mark cells as unvisited, and reset previous pointers.
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
dist[i][j] = INF;
visited[i][j] = 0;
prev[i][j].x = -1;
prev[i][j].y = -1;
}
}
// Define start and end positions (S at top-left and E at bottom-right)
Point start = {0, 0};
Point end = {ROWS - 1, COLS - 1};
dist[start.x][start.y] = 0;
int iteration = 0;
Point current = {-1, -1};
// Main loop: continue until there is no reachable unvisited cell.
while (1) {
// Find the unvisited cell with the smallest tentative distance.
int minDist = INF;
int found = 0;
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (!visited[i][j] && dist[i][j] < minDist) {
minDist = dist[i][j];
current.x = i;
current.y = j;
found = 1;
}
}
}
// If no cell is found or the smallest distance is INF, then exit.
if (!found || minDist == INF) {
break;
}
// Mark the current cell as visited.
visited[current.x][current.y] = 1;
// Visualize this iteration.
clearScreen();
printf("Iteration %d (Processing cell [%d, %d] with distance %d):\n",
iteration++, current.x, current.y, dist[current.x][current.y]);
printVisualization(visited, dist, current, start, end);
sleepMilliseconds(500);
// If we have reached the destination, stop.
if (current.x == end.x && current.y == end.y) {
break;
}
// Explore the four neighbors (up, down, left, right).
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int nx = current.x + dx[k];
int ny = current.y + dy[k];
// Skip out-of-bounds or obstacle cells.
if (nx < 0 || nx >= ROWS || ny < 0 || ny >= COLS)
continue;
if (grid[nx][ny] == '#')
continue;
// If a shorter path to neighbor is found, update its distance and record the path.
if (!visited[nx][ny] && dist[current.x][current.y] + 1 < dist[nx][ny]) {
dist[nx][ny] = dist[current.x][current.y] + 1;
prev[nx][ny] = current;
}
}
}
// Reconstruct the shortest path if one was found.
if (dist[end.x][end.y] == INF) {
printf("\nNo path found from S to E!\n");
} else {
// Trace back from the end to the start.
int pathLength = 0;
Point path[ROWS * COLS];
Point trace = end;
while (!(trace.x == start.x && trace.y == start.y)) {
path[pathLength++] = trace;
trace = prev[trace.x][trace.y];
}
path[pathLength++] = start; // Add the start cell.
// Create a copy of the grid and mark the found path with '*' (except for S and E).
char finalGrid[ROWS][COLS + 1];
for (int i = 0; i < ROWS; i++) {
strcpy(finalGrid[i], grid[i]);
}
for (int i = 0; i < pathLength; i++) {
if ((path[i].x == start.x && path[i].y == start.y) ||
(path[i].x == end.x && path[i].y == end.y))
continue;
finalGrid[path[i].x][path[i].y] = '*';
}
clearScreen();
printf("Final path (length: %d):\n", dist[end.x][end.y]);
for (int i = 0; i < ROWS; i++) {
printf("%s\n", finalGrid[i]);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment