graph.cpp

#include "graph.h"

node* start = NULL;


node* find(int item) {
    node* ptr = start;
    while(ptr != NULL) {
        if(ptr->name == item)
            return ptr;
        ptr = ptr->next;
    }
    return NULL;
}


void insert_node(int node_name) {
    node* tmp = new node;
    tmp->name = node_name;
    tmp->next = NULL;
    tmp->adj = NULL;

    if(start == NULL) {
        start = tmp;
        return;
    }
    node* pt = start;
    while(pt->next != NULL)
        pt = pt->next;
    pt->next = tmp;
}



void insert_edge(int u, int v, int weight) {
    node* locu = find(u);
    node* locv = find(v);

    if(locu == NULL) {
        cout << "Source node " << u << " not present. Insert it first.\n";
        return;
    }
    if(locv == NULL) {
        cout << "Destination node " << v << " not present. Insert it first.\n";
        return;
    }

    Edge* tmp = new Edge;
    tmp->dest = v;
    tmp->weight = weight;  // set weight
    tmp->link = NULL;

    if(locu->adj == NULL) {
        locu->adj = tmp;
        return;
    }

    Edge* ptr = locu->adj;
    while(ptr->link != NULL)
        ptr = ptr->link;
    ptr->link = tmp;
}





void setDeliveryGraph(){
	for (int i = 0; i < 6; ++i){
        insert_node(i);		
	}
	
    insert_edge(0, 1, 2); 
	insert_edge(0, 2, 3); 
	insert_edge(0, 3, 5); 
	insert_edge(0, 5, 4);
    insert_edge(1, 0, 2); 
	insert_edge(1, 5, 1);
    insert_edge(2, 0, 3); 
	insert_edge(2, 3, 1);
    insert_edge(3, 0, 5); 
	insert_edge(3, 4, 2); 
	insert_edge(3, 5, 2); 
	insert_edge(3, 2, 1);
    insert_edge(4, 3, 2); 
	insert_edge(4, 5, 2);
    insert_edge(5, 0, 4); 
	insert_edge(5, 1, 1); 
	insert_edge(5, 3, 2); 
	insert_edge(5, 4, 2);
}




void dijkstra(int source, int dist[]) {
    const int INF = INT_MAX;
    const int MAX = 100;
    int visited[MAX] = {0};
    int nodes[MAX];
    int count = 0;

    node* ptr = start;
    while(ptr != NULL) {
        nodes[count++] = ptr->name;
        ptr = ptr->next;
    }

    for (int i = 0; i < MAX; i++)
        dist[i] = INF;
    dist[source] = 0;

    for (int i = 0; i < count; i++) {
        int u = -1, minDist = INF;
        for (int j = 0; j < count; j++) {
            int node = nodes[j];
            if (!visited[node] && dist[node] < minDist) {
                minDist = dist[node];
                u = node;
            }
        }

        if (u == -1) break;
        visited[u] = 1;

        node* uNode = find(u);
        Edge* e = uNode->adj;
        while (e != NULL) {
            int v = e->dest;
            if (!visited[v] && dist[u] + e->weight < dist[v])
                dist[v] = dist[u] + e->weight;
            e = e->link;
        }
    }
}