Реализуй для Dijkstra вывод всех вершин минимального пути: const int INF = 1e9;

class ListNode //элемент списка
{
public:
    int data;
    ListNode* prev, * next;
public:
    ListNode(int data)
    {
        this->data = data;
        this->prev = this->next = NULL;
    }
};
class LinkedList //список
{
public:
    ListNode* head;

public:
    LinkedList() //1.Инициализация
    {
        head = NULL;
    }

    void freeMemory() //2.Освобождение памяти 
    {
        if (head == NULL)
            return;

        ListNode* current = head;

        ListNode* nextNode;

        do
        {
            nextNode = current->next;
            delete current;
            current = nextNode;
        } while (current != head);
        head = NULL;
    }

    void addSorted(int data) //3.Добавление элемента в порядке возрастания
    {
        ListNode* newNode = new ListNode(data);

        if (head == NULL) //если список пустой
        {
            head = newNode;
            newNode->next = newNode->prev = newNode;
        }
        else if (data < head->data) //если новый элемент меньше головы списка
        {

            newNode->next = head;
            newNode->prev = head->prev;
            head->prev->next = newNode;
            head->prev = newNode;
            head = newNode;
        }
        else if (data > head->prev->data) //если новый элемент больше хвоста списка
        {
            newNode->next = head;
            newNode->prev = head->prev;
            head->prev->next = newNode;
            head->prev = newNode;
            head->prev = newNode;
        }
        else //если новый элемент располагается где-то в середине списка
        {
            ListNode* current = head->next;

            while (current != head && current->data < data) //поиск элемента, значение которого больше нового
            {
                current = current->next;
            }

            newNode->next = current;
            newNode->prev = current->prev;
            current->prev->next = newNode;
            current->prev = newNode;
        }
    }

    void removeBefore(int data) //4.Удаление элемента перед каждым вхождением заданного
    {
        if (head == NULL)
        {
            return;
        }


        if (head->data == data)
        {
            if (head->prev->data == head->next->data)
            {
                head = NULL;
                return;
            }
            else
            {
                ListNode* nodeToRemove = head->prev;
                nodeToRemove->prev->next = head;
                head->prev = nodeToRemove->prev;
                delete nodeToRemove;
            }
        }

        ListNode* current = head->next;

        while (current != head)
        {
            if (current->data == data)
            {
                ListNode* nodeToRemove = current->prev;
                nodeToRemove->prev->next = current;
                current->prev = nodeToRemove->prev;
                delete nodeToRemove;
            }

            current = current->next;
        }
    }

    void remove(int data) //Удаление заданного элемента
    {
        if (head == NULL)
        {
            return;
        }

        if (head->data == data)
        {
            if (head->prev->data == head->next->data && head->data == head->next->data)
            {
                head = NULL;
                return;
            }
            else
            {
                ListNode* nodeToRemove = head;
                head->next->prev = head->prev;
                head->prev->next = head->next;
                head = head->next;
                delete nodeToRemove;
            }
        }

        ListNode* current = head->next;

        while (current != head)
        {
            if (current->data == data)
            {
                ListNode* nodeToRemove = current;
                current->next->prev = current->prev;
                current->prev->next = current->next;
                current = current->next;
                delete nodeToRemove;
            }
            else
                current = current->next;
        }
    }

    bool search(int data) //5.Поиск заданного элемента по значению
    {
        if (head == NULL)
            return false;

        ListNode* current = head;

        do
        {
            if (current->data == data)
                return true;

            current = current->next;
        } while (current != head);

        return false;
    }

    void print() //6.Печать
    {
        if (head == NULL)
            return;

        ListNode* current = head;

        do
        {
            cout << current->data << " ";
            current = current->next;
        } while (current != head);
    }

    LinkedList difference(LinkedList list1, LinkedList list2) //7.Дополнительная операция – разность двух списков
    {
        if (head != NULL)
        {
            LinkedList result;

            ListNode* current = list1.head;

            do
            {
                if (list2.search(current->data) == false)
                    result.addSorted(current->data);
                current = current->next;
            } while (current != list1.head);
            return result;
        }
    }
};

struct Edge
{
    int dst;
    int wght;
};
class GraphNode
{
public:
    int id;
    vector<Edge> edgesfrom;
    LinkedList* adjList;
    int mindist;
    vector<int> minpathNodes;
    bool visited;
public:
    GraphNode(int id)
    {
        this->id = id;
        this->adjList = new LinkedList();
    }
};

class Graph
{
private:
    int V;

public:
    GraphNode** nodes;
    Graph(int V)
    {
        this->V = V;
        nodes = new GraphNode* [V];
        for (int i = 0; i < V; i++)
        {
            nodes[i] = new GraphNode(i);
        }
    }

    void addEdge(int src, int dest, int weight)
    {
        if (src < 0 || src >= V || dest < 0 || dest >= V)
        {
            cout << "Invalid source or destination node" << endl;
            return;
        }
        else if (weight < 0)
        {
            cout << "Weight is negative" << endl;
        }
        else
        {
            nodes[src]->adjList->addSorted(dest);
            Edge e;
            e.dst = dest;
            e.wght = weight;
            nodes[src]->edgesfrom.push_back(e);
        }
    }

    void printGraph()
    {
        for (int i = 0; i < V; i++)
        {
            cout << "Node " << nodes[i]->id << " is connected to : ";
            nodes[i]->adjList->print();
            cout << endl;
        }
    }

    void Dijkstra(int start, int end)
    {
        vector<int> path;
        for (int i = 0; i < V; i++)
        {
            nodes[i]->mindist = INF;
            nodes[i]->visited = false;
            nodes[i]->minpathNodes.clear();
        }
        nodes[start]->mindist = 0;
        for (int j = 0; j < nodes[start]->edgesfrom.size(); j++)
        {
            Edge currEdge = nodes[start]->edgesfrom[j];
            nodes[currEdge.dst]->mindist = currEdge.wght;
            nodes[currEdge.dst]->minpathNodes.push_back(start);
        }
        nodes[start]->visited = true;

        for (int i = 1; i < V; i++)
        {
            for (int j = 0; j < nodes[i]->edgesfrom.size(); j++)
            {
                Edge currEdge = nodes[i]->edgesfrom[j];
                if ((currEdge.wght + nodes[i]->mindist) < nodes[currEdge.dst]->mindist)
                    nodes[currEdge.dst]->mindist = (currEdge.wght + nodes[i]->mindist);
            }
            nodes[i]->visited = true;
        }
        std::cout << "Minimal distance: " << nodes[end]->mindist << endl;
    }
};