Graph Mate!

[ravenscry]

Hi, I'm new to graphs, and I need to build one. The graph is a weighted graph that holds some number of city names with edges linking them together. (And it needs to be randomly )Each edge will have a weight (hopefully) equivalent to the driving distance between the two places.

As for functionality, the user should be able to set a starting point and a destination, and then the function should send back the shortest route between the two and its weight u know.

Ok,now I know how graphs work but how do i do apply it ?

[jonnin]

if you had a way to store a bunch of things that each had a <city1, city2, distance> that was easy to search... what could you do?

[dhayden]

A graph is a collection of nodes:

struct Graph {
    vector<Node> nodes;
};

A node has the name of the city and a collection of edges.

struct Node {
    string name;
    vector<Edge> edges;
};

An edge connects two cities and has a weight. To identify the cities, let's use their index into Graph.nodes.

struct Edge {
    unsigned src, dst;   // index into graph.nodes
    unsigned weight;
};

[tpb]

Creating a random graph can be as simple as filling a square array of ints with random values. To model your problem, the graph would be undirected, which in terms of the square array means it reflects along the main diagonal. Also the weights along the main diagonal would be 0. If the cities are not directly connected then the distance is "infinity", represented in the example below by an X.

   0  1  2  3  4
0  0  3  7  2  3
1  3  0  5  4  X
2  7  5  0  X  6
3  2  4  X  0  4
4  3  X  6  4  0

And presumably you want to apply something like Dijkstra's shortest path algorithm.