NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used.

Example of Disjktra algorithm using heap.

disjktra_heap.c:

```/*
* Program: 09
* Author: Alejandro G. Carlstein
* Description: Disjktra Algorithm using heap
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <errno.h>
#include <string.h>
#include <malloc.h>
#include <limits.h>

#define MAX_EDGES 100001
#define MAX_VERTICES  500001
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define DIV_BY_2(i) (i >> 1)
#define FALSE 0
#define TRUE 1

#define DBG_LV0 0
#define DBG_LV1 0
#define DBG_LV2 0
#define DBG_LV3 0

struct Edge{
int startVertex;
int endVertex;
unsigned int length;
} edges[MAX_EDGES];

struct Vertex{
unsigned int id;
unsigned int weight;
struct Vertex *predecessor;
short visited;
} vertices[MAX_VERTICES];

struct Vertex *vertexPointer;
int edgeIndex;

void init(void);
void printEdges(void);
void disjktraAlgorithm(void);
void initializeSingleSource(void);
void printVertices(void);
void makePriorityQueue(int heapArray[], int *length);
void printArray(int array[], int length);
void buildMinHeap(int heapArray[], int length);
void minHeapify(int heapArray[], int index, int heapSize);
int heapExtractMin(int heapArray[], int *heapSize);
void exchange(int *a, int *b);
void relax(int startVertex, int endVertex, int edge);
void printRoute(void);
void debug(int debugLevel, char *fmt, ...);
void errorDoExit(char *fmt, ...);

int numVertices, numEdges;
int main(int argc, char *argv[]){

init();
disjktraAlgorithm();
printVertices();
return 0;
}

void init(void){
debug(DBG_LV0, 'init()');
}

scanf('%d %d', &numVertices, &numEdges);
debug(DBG_LV1, '# of vertices: %d, # of edges: %d', numVertices, numEdges);
printEdges();
}

void printEdges(void){
debug(DBG_LV0, 'printEdges()');

int i;
for(i = 0; i < numEdges; ++i){
scanf('%d %d %d', &edges[i].startVertex, &edges[i].endVertex, &edges[i].length);
debug(DBG_LV1, '[%d](%d <%d> %d)', i, edges[i].startVertex, edges[i].length, edges[i].endVertex);
}
}

// Disjktra(G, w, s)	//s is source vertex - w is weight
void disjktraAlgorithm(void){
debug(DBG_LV0, 'disjktraAlgorithm()');

// InitializeSingleSource(G, s);
initializeSingleSource();

//	S <- 0    // It will hold vertices

//	Q <- V[G] // Make a priority Queue for the vertices
int heapArray[numVertices];
int heapLength = 0;
makePriorityQueue(heapArray, &heapLength);

//	while Q != 0
while(heapLength > 0){

//		do u <- extractMin(Q)
if (DBG_LV1) printArray(heapArray, heapLength);
int vertexIndex = heapExtractMin(heapArray, &heapLength);
debug(DBG_LV1, '[!]vertex[%d] Weight: %d\n', vertexIndex, vertices[vertexIndex].weight);
if (DBG_LV1) printArray(heapArray, heapLength);

//S <- S U {u}

//		for each vertex v e Adj[u]
//			do relax(u, v, w);
}
vertices[vertexIndex].visited = TRUE;
}

}

void initializeSingleSource(void){
debug(DBG_LV0, 'initializeSingleSource()');

int i;
for(i = 0; i < numVertices; ++i){
vertices[i].id = i;
vertices[i].weight = INT_MAX;
vertices[i].predecessor = NULL;	// p[v] predecessor that is either another vertex or NULL
vertices[i].visited = FALSE;
}
vertices[0].weight = 0;

if (DBG_LV1) printVertices();

if (DBG_LV1){
debug(DBG_LV1, '*List of all adj. vertices*');
for (i = 0; i < numVertices; ++i)
}

}

void printVertices(void){
debug(DBG_LV0, 'printVertices()');

printf('[ ]');
int i;
for (i = 0; i < numVertices; ++i)
printf('[%d]', i);

if (DBG_LV1){
printf('\n[i]');
for (i = 0; i < numVertices; ++i)
printf(' %d ' , vertices[i].id);
}

printf('\n[W]');
for (i = 0; i < numVertices; ++i)
if (vertices[i].weight == INT_MAX){
printf(' ! ');
}else{
printf(' %d ' , vertices[i].weight);
}

if(DBG_LV1){
printf('\n[*]');
for (i = 0; i < numVertices; ++i)
if (vertices[i].predecessor == NULL){
printf(' N ');
}else{
printf(' %d ' , (int)vertices[i].predecessor->id);
}
}

if(DBG_LV1){
printf('\n[V]');
for (i = 0; i < numVertices; ++i)
if (vertices[i].visited == TRUE){
printf(' Y ');
}else{
printf(' N ');
}
}

printf('\n');
}

int vertexIndex;
for (vertexIndex = 0; vertexIndex < numVertices; ++vertexIndex){
}
}

debug(DBG_LV1, ' Searching for adjacent Vertices');
int edgeIndex;
for (edgeIndex = 0; edgeIndex < numEdges; ++edgeIndex){

int startVertex = edges[edgeIndex].startVertex;
int endVertex = edges[edgeIndex].endVertex;
debug(DBG_LV1, '  Edge[%d](%d <%d> %d)', edgeIndex, startVertex, edges[edgeIndex].length, endVertex);

debug(DBG_LV1, '  (startVertex (%d) == (%d) vertexIndex)?', startVertex, vertexIndex);
if (startVertex == vertexIndex){
debug(DBG_LV1, '   YES');
}
}
}

}else{
}
}

debug(DBG_LV1, 'Adjacent Vertices of Vertex: %d', vertexIndex);

}else{

printf('[%d]', vertexIndex);
int i = 0;
printf('[%d]', i++);
}

printf('\n[i]');
}

printf('\n[W]');
printf(' ! ');
}else{
}
}

printf('\n[*]');
printf(' N ');
}else{
}
}

printf('\n[V]');
printf(' Y ');
}else{
printf(' N ');
}
}

printf('\n');
}
}

void makePriorityQueue(int heapArray[], int *length){
debug(DBG_LV0, 'makePriorityQueue(length: %d)', *length);

int i;
for (i = 0; i < numVertices; ++i)
heapArray[i] = i;

*length = numVertices;
if (DBG_LV1) printArray(heapArray, *length);
buildMinHeap(heapArray, *length);
if (DBG_LV1) printArray(heapArray, *length);
if (DBG_LV1) printVertices();
}

void printArray(int array[], int length){
debug(DBG_LV0, 'printArray(length: %d)', length);

int i;
for (i = 0; i < length; ++i)
printf('[%d]', i);

printf('\n');
for (i = 0; i < length; ++i)
printf(' %d ', array[i]);
printf('\n');
}

void buildMinHeap(int heapArray[], int length){
debug(DBG_LV0, 'buildMinHeap(length: %d)', length);

int heapSize = length;

int index;
for (index = DIV_BY_2(length); index > -1; --index)
minHeapify(heapArray, index, heapSize);
}

void minHeapify(int heapArray[], int index, int heapSize){
debug(DBG_LV2, 'minHeapify(index: %d, heapSize: %d)', index, heapSize);

int smallestIndex = index;
int leftIndex = LEFT(index);
int rightIndex = RIGHT(index);
debug(DBG_LV1, '-SmallestIndex: %d, leftIndex: %d, rightIndex: %d', smallestIndex, leftIndex, rightIndex);

if (leftIndex <= heapSize && rightIndex <= heapSize){

unsigned int indexValue = vertices[heapArray[index]].weight;
debug(DBG_LV1,
'INDEX: vertices[heapArray[%d]: %d].id: %d, .weight: %d',
index, heapArray[index], vertices[heapArray[index]].id,
indexValue);

unsigned int leftValue = vertices[heapArray[leftIndex]].weight;
debug(DBG_LV1,
'LEFT VALUE: vertices[heapArray[%d]: %d].id: %d, .weight: %d',
leftIndex, heapArray[leftIndex], vertices[heapArray[leftIndex]].id,
leftValue);

if ((leftIndex < heapSize) && (leftValue < indexValue))
smallestIndex = leftIndex;

debug(DBG_LV1, 'smallestIndex: %d', smallestIndex);

unsigned int rightValue = vertices[heapArray[rightIndex]].weight;

debug(DBG_LV1,
'LEFT VALUE: vertices[heapArray[%d]: %d].id: %d, .weight: %d',
rightIndex, heapArray[rightIndex], vertices[heapArray[rightIndex]].id,
rightValue);

if ((rightIndex < heapSize) && (rightValue < indexValue))
smallestIndex = rightIndex;

debug(DBG_LV1, 'smallestIndex: %d', smallestIndex);

if (smallestIndex != index){
exchange(&heapArray[index], &heapArray[smallestIndex]);
minHeapify(heapArray, smallestIndex, heapSize);
}
}
}

int heapExtractMin(int heapArray[], int *heapSize){
debug(DBG_LV0, 'heapExtractMin(heapSize: %d)', *heapSize);

if (*heapSize < 1)
errorDoExit('Heap Underflow');

buildMinHeap(heapArray, *heapSize);

int min = heapArray[0];
--*heapSize;
heapArray[0] = heapArray[*heapSize];
minHeapify(heapArray, 1, *heapSize);

return min;
}

void exchange(int *a, int *b){
debug(DBG_LV3, 'exchange(a: %d, b: %d)', *a, *b);

int temp;
temp = *a;
*a = *b;
*b = temp;
}

if (vertexList == NULL){
}else{
}
}

void relax(int startVertex, int endVertex, int edgeIndex){
debug(DBG_LV0, 'relax(startVertex: %d, endVerted: %d, edgeIndex: %d)', startVertex, endVertex, edgeIndex);

unsigned int weight = vertices[startVertex].weight + edges[edgeIndex].length;

debug (DBG_LV1, 'vertices[%d].weight(%d) > (%d)weight', endVertex, vertices[endVertex].weight, weight);
if (vertices[endVertex].weight > weight){
vertices[endVertex].weight = weight;
vertices[endVertex].predecessor = &vertices[startVertex];
}
}

void debug(int debugLevel, char *fmt, ...){
if (debugLevel){
va_list argp;
fprintf(stdout, '[DBG] ');
va_start(argp, fmt);
vfprintf(stdout, fmt, argp);
va_end(argp);
fprintf(stdout, '\n');
}
}

void errorDoExit(char *fmt, ...){
va_list argp;
fprintf(stderr, '[Error] ');
va_start(argp, fmt);
vfprintf(stderr, fmt, argp);
va_end(argp);
if (errno){
fprintf(stderr, '=> %s\n', strerror(errno));
}else{
fprintf(stderr, '\n');
}
exit(1);
}```

input.txt:

```8 11
0 1 1
4 5 1
1 5 2
2 5 2
5 6 2
0 3 2
3 4 3
5 7 3
4 2 4
4 6 4
1 2 5```

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.