Реализуй для 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;
}
};