How do I make a NODE GRAPH to use with Dijkstra's Shortest Path?

Question

I am playing around with Dijkstra's Algorithm and have found many sites and code snippets about it and think I would be able to get a grip on it, but I have found no information on how to build the graph itself. Maybe I do not know the correct terms for a google search, but I just cannot find any information on how to build the grpah it self to graph though.

I am making as a learning project, a small c++ Pac-Man game and wish to use this algorithm to control the ghosts that follow pac-man. I have a map (bitmap) and want to place a "node" at each intersection on the maze.

How do I do this? This is the bit I can not understand. How to build the graph itself ?

Is there a visual graph editor maybe? Any advise would be great.

Answer 1

It's all abstract. As such, I'll describe how I'm doing graphs in my android game. Ultimately you can define it anyway you want, but here's my implementation.

A little background, the game is a tower defense and the graph represents paths that the enemies walk on as they make their way from a source to a sink. It wouldn't take much for me to write Dijkstra's algo for my model. I have 3 main classes: Graph, Node, and Connection.

The Graph is the main object. It holds a list of Nodes and a list of Connections. This class has methods like addConnection(Node n1, Node n2, int magnitude) (this is how I actually build the graph), getAllSinks(), getAllSources(), and getNeighbors(Node n) (returns all nodes that share a connection with the parameter node). This is probably where a findShortestPath(Node start, Node stop) method would go.

Since it's a game, a Node has the X and Y of its location on the screen. A Node also has a NodeType which is an enum for Source, Sink, and Normal (and other game related uses like towers). The NodeType is not required for dijkstra.

My Connection is a 1 to 1 link from one Node to another Node and it's bi-directional. You could make it directional if you make a distinction between the two Node endpoints, I just don't need to do that in my game. The Connection stores the Weight of the connection. In my case, I weighted my graph as distance from the sources so enemies can always try and take the "heaviest" path to try and make it to a sink, e.g. the end of the path of a tower defense. The weight could be distance or anything you want. This class has methods like getOtherEndpoint(Node n), getBothEndpoints(), and getWeight().

All of these classes are my own construction. They don't inherit from anything. You can build them exactly how you want them and tie any information you need to any piece of the graph. This is just my implementation in Java. You could do the same thing in C++ if you want or if you're inspired to write your own then I won't take it badly.

Answer 2

You can think of grids as graphs and search space representations can be shown using graphs:

Block A,B,C,D are nodes of graph and weights between the nodes can represent path distance between nodes.

Answer 3

Graphs can be defined programmatically , the common representations explained below.(Note : For djiksta's algorithm , you would also need to store the weights of the various edges). Say for example the graph has A connected to B (weight = 5), and B connected to C(weight = 1).

1) Adjacency list : Used to represent the edges as lists and is used more commonly for sparse graphs. It will have A->B(5) and B->C(1). (It can be promatically represented as an array of linked lists, where each node of the linked list stores the outgoing vertex identification and weight)

2) Adjacency matrix : It will have a 2 dimensional matrix defined as:

    A B C
A   0 5 0
B   0 0 1
C   0 0 0

EDIT : You could find much more detail at this topcoder tutorial series on graphs : section 1 talks about graph representations and section 3 talks about dijksta' algorithm.