Compare the performance of Single Source Shortest Paths using Greedy method when the graph is represented by adjacency matrix and adjacency lists.

 #include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#include <time.h>

#define MAX 1000

#define INF 999999

// ---------- For Adjacency Matrix ----------

int adjMatrix[MAX][MAX];

// ---------- For Adjacency List ----------

struct Node {

    int vertex;

    int weight;

    struct Node* next;

};

struct Node* adjList[MAX];

// ---------- Utility ----------

void addEdgeMatrix(int u, int v, int w) {

    adjMatrix[u][v] = w;

    adjMatrix[v][u] = w;

}

void addEdgeList(int u, int v, int w) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->vertex = v;

    newNode->weight = w;

    newNode->next = adjList[u];

    adjList[u] = newNode;

    // For undirected graph

    newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->vertex = u;

    newNode->weight = w;

    newNode->next = adjList[v];

    adjList[v] = newNode;

}

// ---------- Dijkstra using Matrix ----------

void dijkstraMatrix(int n, int src) {

    int dist[n], visited[n];

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

        dist[i] = INF;

        visited[i] = 0;

    }

    dist[src] = 0;

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

        int min = INF, u;

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

            if (!visited[i] && dist[i] < min)

                min = dist[i], u = i;

        visited[u] = 1;

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

            if (!visited[v] && adjMatrix[u][v] && dist[u] + adjMatrix[u][v] < dist[v])

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

    }

}

// ---------- Dijkstra using List ----------

void dijkstraList(int n, int src) {

    int dist[n], visited[n];

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

        dist[i] = INF;

        visited[i] = 0;

    }

    dist[src] = 0;

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

        int min = INF, u;

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

            if (!visited[i] && dist[i] < min)

                min = dist[i], u = i;

        visited[u] = 1;

        struct Node* temp = adjList[u];

        while (temp) {

            int v = temp->vertex;

            int weight = temp->weight;

            if (!visited[v] && dist[u] + weight < dist[v])

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

            temp = temp->next;

        }

    }

}

// ---------- Random Graph Generator ----------

void generateGraph(int n, int edges) {

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

        adjList[i] = NULL;

        for (int j = 0; j < n; j++) adjMatrix[i][j] = 0;

    }

    int u, v, w;

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

        u = rand() % n;

        v = rand() % n;

        if (u != v && adjMatrix[u][v] == 0) {

            w = rand() % 100 + 1;

            addEdgeMatrix(u, v, w);

            addEdgeList(u, v, w);

        } else i--;

    }

}

// ---------- Main ----------

int main() {

    srand(time(NULL));

    int vertices = 1000;

    int edges = 3000;

    generateGraph(vertices, edges);

    clock_t start, end;

    double timeMat, timeList;

    start = clock();

    dijkstraMatrix(vertices, 0);

    end = clock();

    timeMat = ((double)(end - start)) / CLOCKS_PER_SEC * 1000;

    start = clock();

    dijkstraList(vertices, 0);

    end = clock();

    timeList = ((double)(end - start)) / CLOCKS_PER_SEC * 1000;

    printf("Vertices: %d, Edges: %d\n", vertices, edges);

    printf("Time using Adjacency Matrix: %.2f ms\n", timeMat);

    printf("Time using Adjacency List:   %.2f ms\n", timeList);

    return 0;

}

Output: