I want to implement Dijkstra's Algorithm in C++ with Adjacency List

Question

I have a C++ code snippet that represents a weighted graph using an adjacency list. The code successfully creates vertices, adds weighted edges between them, and displays the vertices along with their respective edges. However, I'm struggling to implement Dijkstra's Algorithm within this existing codebase.

Here's the current structure of the code:

#include<iostream>
using namespace std;

// Structure for representing an edge in the graph
struct edge {
    int weight;        // Weight of the edge
    string data;       // Data of the connected vertex
    edge* next;        // Pointer to the next edge
};

// Structure for representing a vertex in the graph
struct node {
    string data;       // Data of the vertex (city name)
    edge* head;        // Pointer to the first edge connected to the vertex
    edge* tail;        // Pointer to the last edge connected to the vertex
    node* next;        // Pointer to the next vertex in the graph
} *head = NULL, *tail = NULL;

// Function to insert a new vertex into the graph
void insert_vertex(string cityName) {
    node* temp = new node;
    temp->data = cityName;
    temp->head = NULL;
    temp->tail = NULL;

    if (head == NULL) {
        temp->next = NULL;
        head = tail = temp;
    }
    else {
        tail->next = temp;
        tail = temp;
        tail->next = NULL;
    }
}

// Function to check if a vertex with a given data exists in the graph
bool check_uname(string data) {
    node* temp = head;
    while ((temp->data != data) && (temp != tail)) {
        temp = temp->next;
    }
    if (temp->data != data) {
        cout << "Second Vertex Not Found " << data << endl;
        return false;
    }
    return true;
}

// Function to add a weighted edge between two vertices in the graph
void add_edge(string vname, string uname, int weight) {
    node* temp = head;
    while (temp != NULL && temp->data != vname) {
        temp = temp->next;
    }
    if (temp == NULL) {
        cout << "Source Vertex Not Found" << endl;
        return;
    }

    if (temp != NULL && check_uname(uname)) {
        edge* etemp = new edge;
        etemp->data = uname;
        etemp->weight = weight;

        if (temp->head == NULL) {
            etemp->next = NULL;
            temp->head = temp->tail = etemp;
        }
        else {
            temp->tail->next = etemp;
            temp->tail = etemp;
            etemp->next = NULL;
        }
    }
}

// Function to display the vertices and edges in the graph
void display() {
    node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        edge* etem = temp->head;
        while (etem != NULL) {
            cout << "(" << etem->data << ", " << etem->weight << ") ";
            etem = etem->next;
        }
        temp = temp->next;
        cout << endl;
    }
}

// [Your Dijkstra's Algorithm implementation here]

int main() {
    // Example usage of the functions

    // Inserting vertices
    insert_vertex("City1");
    insert_vertex("City2");
    insert_vertex("City3");
    insert_vertex("City4");
    insert_vertex("City5");

    // Adding weighted edges between vertices
    add_edge("City1", "City2", 3);
    add_edge("City2", "City3", 5);
    add_edge("City1", "City4", 2);

    // Displaying the graph
    cout << "Vertices   Edges\n";
    display();

    // [Your Dijkstra's Algorithm function call here]

    return 0;
}

In this code, I've defined structures for vertices and edges and implemented functions for creating vertices, adding weighted edges, and displaying the graph.

Could someone help guide me on how to integrate Dijkstra's Algorithm into this existing code to find the shortest path between two cities (vertices)? I'm specifically seeking assistance with the algorithm's implementation within this adjacency list representation.

Any insights, code snippets, or guidance would be greatly appreciated!

Thank you

.