Shortest path through sudo-linked list

Hello everyone,
Ill start out by saying im not an extremely experience programmer by any means.

I am needing to code a shorted path algorithm through a sort of sudo-linked list. I say sudo because its not a true linked list as in *next *prev.

The Data in memory that i need to do this through is in memory via a class.

The important parts of the class is one element is just an int that tells me the current node number, the second is an int that tells me how many neighbors this node has, and the third is a vector of ints containing the number of the neighboring nodes.

the vector was needed because each node type can have a different amount of neighbors

For example if the class data looks like this:

0 1 1

that means that it is node 0, it has 1 neighbor, and the neighboring node is 1

another example:

8 3 1 2 3

means node 8, 3 neighbors, and the neighbors are nodes 1 2 3

I need to find a way to get from 1 node to another using this linked list, and the shortest path if we plan the data points well enough can be determined by how many nodes there are from start to finish.

Can anyone point me in the right direction on how to code this?

P.S i have never done recursion

This kind of "list" is usually called a graph.

A famous algorithm for finding the shortest path in a graph is the Dijkstra's algorithm.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Last edited on
As your `weights' are all the same, you could simply use Breadth-First Search
Topic archived. No new replies allowed.