This is an implementation in blocks of Dijkstra's Shortest Path Algorithm, with a sample graph and test framework.

It is a tool to find the shortest or lowest cost path from one node to another node in a weighted graph.

This has applications in route planning, and might be useful for students wanting to build their own campus map apps.

References:

https://www.google.com/search?q=Dijkstra's+algorithm

This particular implementation is based on C code at

Sample run:

Input graph, in sparse (one row per edge) form:

## Sample CSV File

```
Node1,Node2,Distance
0,1,4
0,7,8
1,0,4
1,7,11
1,2,8
7,0,8
7,1,11
7,8,7
7,6,1
2,1,8
2,8,2
2,5,4
2,3,7
8,2,2
8,6,6
8,7,7
6,7,1
6,8,6
6,5,2
3,2,7
3,4,9
3,5,14
4,3,9
4,5,10
5,6,2
5,2,4
5,3,14
5,4,10
```

Please note that the nodes don't have to be numbers (0-8).

They can be place names (columns 1 and 2) (PoeHall302, Boston, NYC, Paris, etc.) and the costs (column 3) can be your own measures in a common measure like time or distance or air fare.

## Equivalent C code

Equivalent C code:

```
// Implementation of Dijkstra's Algorithm in C
// importing the standard I/O header file
#include <stdio.h>
// defining some constants
#define INF 9999
#define MAX 10
// prototyping of the function
void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start);
// defining the function for Dijkstra's Algorithm
void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) {
int cost[MAX][MAX], distance[MAX], previous[MAX];
int visited_nodes[MAX], counter, minimum_distance, next_node, i, j;
// creating cost matrix
for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
if (Graph[i][j] == 0)
cost[i][j] = INF;
else
cost[i][j] = Graph[i][j];
for (i = 0; i < size; i++) {
distance[i] = cost[start][i];
previous[i] = start;
visited_nodes[i] = 0;
}
distance[start] = 0;
visited_nodes[start] = 1;
counter = 1;
while (counter < size - 1) {
minimum_distance = INF;
for (i = 0; i < size; i++)
if (distance[i] < minimum_distance && !visited_nodes[i]) {
minimum_distance = distance[i];
next_node = i;
}
visited_nodes[next_node] = 1;
for (i = 0; i < size; i++)
if (!visited_nodes[i])
if (minimum_distance + cost[next_node][i] < distance[i]) {
distance[i] = minimum_distance + cost[next_node][i];
previous[i] = next_node;
}
counter++;
}
// printing the distance
for (i = 0; i < size; i++)
if (i != start) {
printf("\nDistance from the Source Node to %d: %d", i, distance[i]);
}
}
// main function
int main() {
// defining variables
int Graph[MAX][MAX], i, j, size, source;
// declaring the size of the matrix
size = 7;
// declaring the nodes of graph
Graph[0][0] = 0;
Graph[0][1] = 4;
Graph[0][2] = 0;
Graph[0][3] = 0;
Graph[0][4] = 0;
Graph[0][5] = 8;
Graph[0][6] = 0;
Graph[1][0] = 4;
Graph[1][1] = 0;
Graph[1][2] = 8;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 11;
Graph[1][6] = 0;
Graph[2][0] = 0;
Graph[2][1] = 8;
Graph[2][2] = 0;
Graph[2][3] = 7;
Graph[2][4] = 0;
Graph[2][5] = 4;
Graph[2][6] = 0;
Graph[3][0] = 0;
Graph[3][1] = 0;
Graph[3][2] = 7;
Graph[3][3] = 0;
Graph[3][4] = 9;
Graph[3][5] = 14;
Graph[3][6] = 0;
Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 0;
Graph[4][3] = 9;
Graph[4][4] = 0;
Graph[4][5] = 10;
Graph[4][6] = 2;
Graph[5][0] = 0;
Graph[5][1] = 0;
Graph[5][2] = 4;
Graph[5][3] = 14;
Graph[5][4] = 10;
Graph[5][5] = 0;
Graph[5][6] = 2;
Graph[6][0] = 0;
Graph[6][1] = 0;
Graph[6][2] = 0;
Graph[6][3] = 0;
Graph[6][4] = 2;
Graph[6][5] = 0;
Graph[6][6] = 1;
source = 0;
// calling the DijkstraAlgorithm() function by passing the Graph, the number of nodes and the source node
DijkstraAlgorithm(Graph, size, source);
return 0;
}
```

Source:

Dijkstras_algorithm.aia (213.5 KB)

Blocks: