Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0125· OpenAIAi2 WildChat-4.8M (AI2)

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

  1. 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 edgesfrom; LinkedList* adjList; int mindist; vector 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 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; } };

  2. Assistant

    To output all vertices of the minimum path using Dijkstra's algorithm, you can modify the Dijkstra function in the Graph class to store the previous node for each node in the graph.

    Here is the updated Dijkstra function:

    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++)
        {
            int minDist = INF;
            int minIdx = -1;
            for (int j = 0; j < V; j++)
            {
                if (!nodes[j]->visited && nodes[j]->mindist < minDist)
                {
                    minDist = nodes[j]->mindist;
                    minIdx = j;
                }
            }
            
            if (minIdx == -1)
            {
                break; // no more reachable nodes
            }
            
            nodes[minIdx]->visited = true;
            for (int j = 0; j < nodes[minIdx]->edgesfrom.size(); j++)
            {
                Edge currEdge = nodes[minIdx]->edgesfrom[j];
                if ((currEdge.wght + nodes[minIdx]->mindist) < nodes[currEdge.dst]->mindist)
                {
                    nodes[currEdge.dst]->mindist = (currEdge.wght + nodes[minIdx]->mindist);
                    nodes[currEdge.dst]->minpathNodes = nodes[minIdx]->minpathNodes;
                    nodes[currEdge.dst]->minpathNodes.push_back(minIdx);
                }
            }
        }
    
        std::cout << "Minimal distance: " << nodes[end]->mindist << endl;
        std::cout << "Minimum path: ";
        for (int node : nodes[end]->minpathNodes)
        {
            std::cout << node << " -> ";
        }
        std::cout << end << endl;
    }
    

    With this modification, the Dijkstra function will now not only output the minimal distance but also the minimum path by traversing the minpathNodes array.