Dijstra Algorithm

#include <stdio.h>

#include <limits.h>

#define MAX_VERTICES 100

// Function to find the vertex with the minimum distance value

int minDistance(int dist[], int sptSet[], int vertices) {

int min = INT_MAX, minIndex;

for (int v = 0; v < vertices; v++) {

if (!sptSet[v] && dist[v] < min) {

min = dist[v];

minIndex = v;

return minIndex;

// Function to print the constructed distance array

void printSolution(int dist[], int vertices) {

printf("Vertex \tDistance from Source\n");

for (int i = 0; i < vertices; i++) {

printf("%d \t%d\n", i, dist[i]);

// Function to implement Dijkstra's algorithm for a given graph and source vertex

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices) {

int dist[MAX_VERTICES]; // The output array dist[i] holds the shortest distance from src to i

int sptSet[MAX_VERTICES]; // sptSet[i] will be true if vertex i is included in the shortest path tree or the shortest
distance from src to i is finalized

// Initialize all distances as INFINITE and sptSet[] as false

for (int i = 0; i < vertices; i++) {

dist[i] = INT_MAX;
 sptSet[i] = 0;

// Distance from source vertex to itself is always 0

dist[src] = 0;

// Find the shortest path for all vertices

for (int count = 0; count < vertices - 1; count++) {

// Pick the minimum distance vertex from the set of vertices not yet processed.

// u is always equal to src in the first iteration.

int u = minDistance(dist, sptSet, vertices);

// Mark the picked vertex as processed

sptSet[u] = 1;

// Update dist value of the adjacent vertices of the picked vertex.

for (int v = 0; v < vertices; v++) {

// Update dist[v] only if it is not in the sptSet, there is an edge from u to v,

// and the total weight of path from src to v through u is smaller than the current value of dist[v]

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {

dist[v] = dist[u] + graph[u][v];

// Print the constructed distance array

printSolution(dist, vertices);

int main() {

int vertices;

// Input the number of vertices

printf("Input the number of vertices: ");

scanf("%d", &vertices);

if (vertices <= 0 || vertices > MAX_VERTICES) {

printf("Invalid number of vertices. Exiting...\n");

int graph[MAX_VERTICES][MAX_VERTICES];

// Input the adjacency matrix representing the weighted graph

printf("Input the adjacency matrix for the graph (use INT_MAX for infinity):\n");

for (int i = 0; i < vertices; i++) {

for (int j = 0; j < vertices; j++) {

scanf("%d", &graph[i][j]);

int source;

// Input the source vertex

printf("Input the source vertex: ");

scanf("%d", &source);

if (source < 0 || source >= vertices) {

printf("Invalid source vertex. Exiting...\n");

return 1;

// Perform Dijkstra's algorithm

dijkstra(graph, source, vertices);

return 0;

Output:

Input the number of vertices: 5

Fractional knapsack Problem

#include <stdio.h>

int n = 5;

int p[10] = {3, 3, 2, 5, 1};

int w[10] = {10, 15, 10, 12, 8};

int W = 10;

int main(){

int cur_w;

float tot_v;

int i, maxi;

int used[10];

for (i = 0; i < n; ++i)

used[i] = 0;

cur_w = W;

while (cur_w > 0) {

maxi = -1;

for (i = 0; i < n; ++i)

if ((used[i] == 0) &&

((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))

maxi = i;

used[maxi] = 1;

cur_w -= p[maxi];

tot_v += w[maxi];
 if (cur_w >= 0)

printf("Added object %d (%d, %d) completely in the bag. Space left: %d.\n", maxi + 1, w[maxi], p[maxi],
cur_w);

else {

printf("Added %d%% (%d, %d) of object %d in the bag.\n", (int)((1 + (float)cur_w/p[maxi]) * 100), w[maxi],
p[maxi], maxi + 1);

tot_v -= w[maxi];

tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];

printf("Filled the bag with objects worth %.2f.\n", tot_v);

return 0;

Output
Added object 5 (8, 1) completely in the bag. Space left: 9.
Added object 2 (15, 3) completely in the bag. Space left: 6.
Added object 3 (10, 2) completely in the bag. Space left: 4.
Added object 1 (10, 3) completely in the bag. Space left: 1.
Added 19% (12, 5) of object 4 in the bag.
Filled the bag with objects worth 45.40.

Job Sequencing with deadline

#include <stdio.h>

#include <stdlib.h>

// A structure to represent a Jobs

typedef struct Jobs {

char id; // Jobs Id

int dead; // Deadline of Jobs

int profit; // Profit if Jobs is over before or on deadline

} Jobs;
// This function is used for sorting all Jobss according to

// profit

int compare(const void* a, const void* b){

Jobs* temp1 = (Jobs*)a;

Jobs* temp2 = (Jobs*)b;

return (temp2->profit - temp1->profit);

// Find minimum between two numbers.

int min(int num1, int num2){

return (num1 > num2) ? num2 : num1;

int main(){

Jobs arr[] = {

{ 'a', 2, 100 },

{ 'b', 2, 20 },

{ 'c', 1, 40 },

{ 'd', 3, 35 },

{ 'e', 1, 25 }

};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Following is maximum profit sequence of Jobs: \n");

qsort(arr, n, sizeof(Jobs), compare);

int result[n]; // To store result sequence of Jobs

bool slot[n]; // To keep track of free time slots

// Initialize all slots to be free

for (int i = 0; i < n; i++)

slot[i] = false;

// Iterate through all given Jobs

for (int i = 0; i < n; i++) {

for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {

// Free slot found

if (slot[j] == false) {

result[j] = i;

slot[j] = true;

break;

// Print the result

for (int i = 0; i < n; i++)

if (slot[i])

printf("%c ", arr[result[i]].id);

return 0;

Output
Following is maximum profit sequence of Jobs:
cad