@
doug4
Careful there... you are picking on stuff that isn’t necessarily wrong, and giving an odd name to a vertex yourself.
@
hixtus
However, there is a valid point in structural organization. The shape of your graph can help or hinder; currently it is hindering you.
In the simplest form, a directed graph can be just a 2D integer array. Here is the graph you have linked in the d0.jpg as an array:
A B C D E F G
A  5 3    
B   2  3  1
C    7 7  
D 2     6 
E    2  1 
F       
G     1  

So, for example, there is an edge from row A to column B with weight 5, meaning A→B = 5.
However, row B to column A has an invalid edge weight, meaning B↛A (B does not go to A).
If I were to implement this in code, I might be tempted to write something like:
1 2 3 4 5 6 7 8 9 10 11 12

#define _ 1
int G[7][7] =
{
{ _, 5, 3, _, _, _, _ },
{ _, _, 2, _, 3, _, 1 },
{ _, _, _, 7, 7, _, _ },
{ 2, _, _, _, _, 6, _ },
{ _, _, _, 2, _, 1, _ },
{ _, _, _, _, _, _, _ },
{ _, _, _, _, 1, _, _ }
};
#undef _
 
Where edge A→B is
G[0][1]
(A==0, B==1).
But, that’s not only oldschool, it can be done
better.
Goals:
• Keep the easy G(u,v) lookup for an edge weight.
• Eliminate “special” values (like 1) by eliminating nonedges.
• Keep easy check for u→v exists
• Keep easy iteration over the graph
First,
indexing.
In your code, you use a std::string for the vertex names. That’s fine. I often do that myself, even though node names in homework assignments like this are typically a
single char. The 2D array thing kind of makes that uncomfortable, but not especially difficult, but who cares? 2D arrays are
so last year.
Since we have decided on a specific type for our vertex names (a std::string), let’s formalize that:

typedef std::string Vertex;
 
And while we are at it, our weight should be typed as well:
Now to think a second. Each
edge in a graph is an association: Vertex
u associates with Vertex
v having weight
w.
In our 2D array, that was easy: row
u to column
v has value
w.
That simple association makes it tempting to write a struct like:
1 2 3 4 5 6

struct BadEdge
{
Vertex u;
Vertex v;
Weight w;
};

Don’t do this, though.
Just say "NO!"  
A graph then could be a list of those:

typedef std::vector<BadEdge> BadGraph;
 
But now we have a problem. With our 2D array, I could easily access any
u→
u edge by simply saying
G[u][v]
.
Except now I need to
search my graph (vector) just to find the right combination of
u and
v!
Thinking hard, I realize that each node may have multiple edges leading from it, and update my struct to this:
1 2 3 4 5 6 7 8

struct BadEdges // node Look familiar?
{ //
Vertex u; // source
std::vector<Vertex> vs; // dests
std::vector<Weight> ws; // costs
};
typedef std::vector<BadEdges> BadGraph;

Hey man, I said "no".  
Great! Now I only have to
search my graph to find
u.
Oh, but then I still have to search
G[index_of_u].vs
to find
v.
Bummer.
Let’s step back, and see if there is a better way.
Remember, we are messing with an
association. In an array, we associate an integer index (0, 1, 2, ...) with the value in the array. In our graph, we do that
twice:
G[0]
gives us access to the first element element of the array:
{ _, 5, 3, _, _, _, _ },
.
That first element is also an array, so there is again an association, this time between an integer index and an edge weight:
{ _, 5, 3, _, _, _, _ }[1]
gives us the weight
5
.
Simply:
G[0][1] == 5
. Right?
The change we wish to make is that we no longer want integertoarray then integertoweight associations. We want a VertextoEdge and EdgetoWeight assocation.
That is:
G["A"] > an Edge
G["A"]["B"] > a Weight
In C++, an arbitrary associative array is called a “map”, and you get one by #including <map>. Once you do, you can make the ‘edge’ association for a whole collection of edges:

typedef std::map<Vertex,Weight> Edges;
 
This easily takes the place of the entire BadEdges struct
and gives us a very convenient lookup pattern. Given a vertex's Edges, we can find any edge by naming the target vertex v:
1 2

Edges es = <obtained from somewhere>;
es["B"] == 5;
 
And just as the 2D array G[0] is a collection of edges leading from vertex
u, we can create a map to do the same:

typedef std::map<Vertex,Edges> Graph;
 
Lookup syntax is now our friend:
1 2

Graph G;
G["A"]["B"] = 5;
 
Beyond that, we can also loop through the edges with ease:
1 2 3

for (auto [u, e] : G) // for each (Vertex u, Edges e) in Graph G
for (auto [v, w] : e) // for each (Vertex v, weight ) in Edges e
std::cout << u << " > " << v << " with weight " << w << "\n";
 
It is also easily possible to test whether an association exists:
1 2 3

if (G.contains("A"))
if (G["A"].contains("B"))
std::cout << "A > B\n";
 
To recap, we now have the following structure:
1 2 3 4 5 6 7

#include <map>
#include <string>
typedef std::string Vertex;
typedef int Weight;
typedef std::map<Vertex,Weight> Edges;
typedef std::map<Vertex,Edges> Graph;
 
Did we accomplish our goals?
• Keep the easy G(u,v) lookup for an edge weight.
Yes.
G[u][v] == w
• Eliminate “special” values (like 1) by eliminating nonedges.
Yes.
If u→v does not exist, there is no u→v association (no memory used) in the graph
• Keep easy check for u→v exists
Yes.
if (G.contains(u) and G[u].contains(v)) ...
• Keep easy iteration over the graph
Yes.
for (auto [u, e] : G)
to iterate over vertices with any outgoing edges
e
for (auto [v, w] : e)
for edges
u→
v with weight
w
Any caveats?
Yes.
G[u][v]
will create nodes and edges if any of
u,
v, or
u→
v do not exist.
Care must be taken to check that everything exists before using
G[u][v]
.
So, what about friggin’ Dijkstra’s Algorithm?!!!
That’s easy. I’ll get back to that next time I post...
Gonna eat lunch now.
The point of this entire post is that
data structure matters.
Of course, you most certainly
canperform Dijkstra’s on your existing structure.
That isn’t the issue, though.
The problem was that your current structure was making it significantly more difficult to reason about your algorithm. It led to:
• naming problems
• additional code (and duplication of code) (to get around structural deficiencies)
• additional objects
All of these are symptoms of struggling to clearly understand the code objectives.
When I get back I’ll take some time to work through Dijkstra’s algorithm in a shockingly simple and clear way. :O)
Because Dijkstra’s algorithm is, actually, brilliantly simple!
(I have been halfheartedly looking for an online video that explains it the way I want, but haven’t found one.)
(And, thinking back, I have surprised myself at how many times I have written an academic implementation of Dijkstra’s algorithm...)