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

Допиши метод Dijkstra так, чтобы он выводил минимальный путь(и вершины, и грани): const…

  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 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;
        }
    
    }
    

    };

  2. 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();