Making Dijkstra's in c++ - priority queue iterator problems

Question

I've just learnt Dijkstra's in school but i wanted to try and code it. I'm having a problem with an iterator and changing a specific point in a vector, but most likely my implementation is wrong. The error I'm getting is below, and I'm wondering how I change a std::pair<Node*, int> to a std::_vector_iterator object. Furthermore, what does _Scary_val mean?

My error:

no suitable conversion function from
  "std::pair<Node *, int>" to
  "std::_Vector_iterator<std::vector<Node *, std::allocator<Node *>>::_Scary_val>::value_type"
  (aka "Node *") exists

My header file

#pragma once
#include <vector>
#include <string>
class Node;
class Graph;
class Edge;

class Edge {
public:
    Node* from;
    Node* to;
    int weight;
    //bool directional;
    Edge() = default;

    Edge(Node* to, Node* from, int weight, bool directional);
};

class Node {
public:
    Node() = default;
    Node(Graph& graph, std::string name);
    std::vector<Edge*> conncections;
    std::string name;
    void printConnections();

};

class Graph {
public:
    Graph() = default;

    std::vector<Node*> GraphNodes;

    void printGraph();
};

void dijkstra(Node* start, Node* end);

My CPP file.

#include "Graphs.h"
#include <iostream>
#include <vector>

Graph graph1;
Node A(graph1, "A");
Node B(graph1, "B");
Node C(graph1, "C");
Node D(graph1, "D");
Node E(graph1, "E");
Node F(graph1, "F");
Node G(graph1, "G");
Node H(graph1, "H");
Node I(graph1, "I");
Node J(graph1, "J");

Node* Aptr = &A;
Node* Bptr = &B;
Node* Cptr = &C;
Node* Dptr = &D;
Node* Eptr = &E;
Node* Fptr = &F;
Node* Gptr = &G;
Node* Hptr = &H;
Node* Iptr = &I;
Node* Jptr = &J;

//A C B D E F G H I
Edge test1(Aptr, Bptr, 50, false);
Edge test2(Aptr, Cptr, 25, false);
Edge test3(Cptr, Eptr, 45, false);
Edge test4(Cptr, Fptr, 50, false);
Edge test5(Bptr, Iptr, 80, false);
Edge test6(Bptr, Dptr, 25, false);
Edge test7(Dptr, Iptr, 70, false);
Edge test8(Dptr, Fptr, 10, false);
Edge test9(Eptr, Gptr, 30, false);
Edge test10(Eptr, Hptr, 35, false);
Edge test11(Gptr, Jptr, 80, false);
Edge test12(Iptr, Jptr, 30, false);

using std::cout;

Edge::Edge(Node* from, Node* to, int weight, bool directional) {
    this->to = to;
    this->from = from;
    this->weight = weight;

    from->conncections.push_back(this);

    if (!(directional)) {
        /*new Edge(to, from, weight, true);*/
    }
}

Node::Node(Graph& graph, std::string name) {
    graph.GraphNodes.push_back(this);
    this->name = name;
}

void Graph::printGraph() { //this will call Node::printConnections
    for (auto& Node : this->GraphNodes) {
        Node->printConnections();
    }
}

void Node::printConnections() {
    for (auto& Node : this->conncections) {
        cout << "{" << Node->from->name << " " << Node->to->name << " " << Node->weight << "} \n";
    }
}


void dijkstra(Node* start, Node* end) {
    start->printConnections(); //prints what start is connected to

    std::vector<std::pair<Node*, int>> finalWeight;

    std::vector<Node*> visited;

    std::vector<std::pair<Node*, int>> notVisited;

    std::pair<Node*, int> current;

    notVisited.emplace_back(std::make_pair(start,0));

    while (!notVisited.empty()) {
        current = notVisited[0]; 
        if (current.first == end)
            break;
        notVisited.erase(notVisited.begin()); //gets rid of that node from the list 
            
        for (auto& node : current.first->conncections) { //goes through connections which hold edges for that node
            
            if (std::find(visited.begin(), visited.end(), node->to) != visited.end())
                continue; //this is checking if the node is already visited

            auto temp = std::make_pair(node->to, node->weight + current.second); 
            int i = 0;
            while (i != notVisited.size() && notVisited[i].second < temp.second) {
                i++;
            }
            notVisited.insert(notVisited.begin() + i, temp); //inserts the element in the right place
            visited.push_back(node->from); //adds it to visited

            auto it = (std::find(visited.begin(), visited.end(), node->to));
            
            if (*it != node->to)
                finalWeight.emplace_back(temp);
            else {
                *it = temp;
            }

        }
    }
    for (int i = 0; i < finalWeight.size(); i++) {
        cout << finalWeight[i].first->name << " " << finalWeight[i].second << "\n";
    }
}

int main() {
    dijkstra(Aptr, Jptr);
}

The actual graph is in the image below

Focus on the syntax error. When your code does not compile, there is no functionality, so it does not really matter what it should do. Take the line with the error, put it in a function, and add whatever declarations and definitions are needed to support that line, and only what is needed. You should end up closer to half a dozen lines of code in your minimal reproducible example. — JaMiT
– JaMiT, Commented Jul 7 at 16:40
*it = temp; looks like it should have been *it = temp.first; and you are missing including at least <algorithm>. — Ted Lyngmo
– Ted Lyngmo, Commented Jul 7 at 17:01
Please include the line number or function name in your error, so readers don't have to verify every single line of the code you posted. — Dominik Kaszewski
– Dominik Kaszewski, Commented Jul 7 at 17:06
"I'm wondering how I change a std::pair<Node*, int> to a std::_vector_iterator object." Read the entire error message! That's an alias for Node *. You're asking how to change a std::pair<Node*, int> to a Node *. — Drew Dormann
– Drew Dormann, Commented Jul 7 at 17:40
@Luke If you don't include <algorithm> your program will depend on implementation details if it compiles or not. By including <algorithm> all conforming standard libraries will provide std::find (and all the other functions declared to be available by including that header). — Ted Lyngmo
– Ted Lyngmo, Commented Jul 7 at 17:52

Ted Lyngmo · Accepted Answer · 2025-07-07 20:44:15Z

2

I found 2 issues with your code that I fixed to make it compile:

Add #include <algorithm> at the top of the c++ file. It defines std::find().
On the line that reads *it = temp it should probably be *it = temp.first.

The second bullet point above is what is causing the error you see. You were tying to assign a std::pair<Node*, int> to a Node*. This is a case where the compiler error for template issues is difficult to understand.

Newer compilers are better though: Here is the error I get with g++ 12:

error: cannot convert ‘std::pair<Node*, int>’ to ‘Node*’ in assignment
  112 |                 *it = temp;
      |                       ^~~~
      |                       |
      |                       std::pair<Node*, int>

If you can, I would suggest updating your compiler version. It can you help out with things like this.

I did not try to see if your code actually works.

edited Jul 7 at 20:44

Ted Lyngmo

124k7 gold badges93 silver badges155 bronze badges

answered Jul 7 at 17:21

OfNothing

6353 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Ted Lyngmo Jul 7 at 17:53

Just out of curiosity: Why did you remove the code formatting that I added to your answer?

OfNothing Jul 7 at 20:42

It was not intentional. I think we may have done a simultaneous edit/ race condition type of thing.

Ted Lyngmo Jul 7 at 20:44

Ok then, I've added the formatting back

Luke Jul 8 at 8:56

I'm using visual studio, is it worth trying to change the compiler i use there? I think i have a version of g++ downloaded, so im probably just using the MSVC compiler, i dont know what version. Futhermore, i can tell you that this code doesnt work even with the errors fixed. I currently dont have any way of holding the shortest path, im just calculating the shortest weights

OfNothing Jul 8 at 15:06

If you are using visual studio as you tool chain for class, It would be likely harder to change than it is worth it. If you look closely at the error message kicked out by MSVC, it tells you the same information that g++ does, just a bit more unfriendly.

Ted Lyngmo Jul 8 at 16:15

@Luke Is this answer acceptable in its current state or is there anything more (related to your original question) that needs clarification?

Luke Jul 9 at 9:26

Marked as completed now sorry.

Collectives™ on Stack Overflow

Making Dijkstra's in c++ - priority queue iterator problems

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related