gpt-3.5-turbo-0125· OpenAI WildChat-4.8M (AI2)
Допиши метод Dijkstra так, чтобы он выводил минимальный путь(и вершины, и грани): const…
- User
Допиши метод 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 edges; LinkedList* adjList; int mindist;
public: GraphNode(int id) { this->id = id; this->adjList = new LinkedList(); } };
class Graph { private: int V; GraphNode** nodes;
public: 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]->edges.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) { for (int i = 0; i < V; i++) { nodes[i]->mindist = INF; } nodes[start]->mindist = 0; if (nodes[start]->edges.size() == 0) { cout << "Not enough connections" << endl; return; } }};
- Assistant
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(0, start)); int pred[V]; // предыдущие вершины fill(pred, pred + V, -1); int dist[V]; fill(dist, dist + V, INF); dist[start] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (size_t i = 0; i < nodes[u]->edges.size(); ++i) { int v = nodes[u]->edges[i].dst; int weight = nodes[u]->edges[i].wght; if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pred[v] = u; pq.push(make_pair(dist[v], v)); } } } LinkedList path; for (int current = end; current != -1; current = pred[current]) { path.addSorted(current); } cout << "Shortest path from node " << start << " to node " << end << ":" << endl; path.print();