Looking for an algorithm to find the shortest path

Question

Basically I have a graph with 12 nodes (representing cities) and 13 edges (representing routes).

Now let's say that (randomly) I have a plan for visiting n nodes, departing from a specific one (A). So (having N <= (12-1)) and then come to the starting point.

For what I've been looking, it seems almost like the Traveling Salesman Problem but with the difference that in my salesman doesn't necessarily needs to visit all nodes.

What algorithm am I looking for?

EDIT

Apparently this is not going to be a TSP, because TSP says that the graph must be closed and we go through every city (node) only once. In my case, it can cross a city more than once, if it makes the route shorter.

A few more examples for what am I looking for:

Example one:

Depart from: A
Need to visit (B,D,E,L,G,J,K)
Come back to: A

Example two:

Depart from: A
Need to visit (B,C,D,G,H,I,J,K)
Come back to: A

Rules:

- Get shortest path
- No specific order
- Can visit one node (city) more than once

Remember, this is for a project in C, so this is just pre-coding research.

Answer 1

There are a lot of algorithms out there doing this. The catchword is path-finding.

The best algorithm to learn from at the beginning is the good old Dijkstra http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Then for larger graphs (that are no maze) you might want an algorithm with some direction heuristics making evaluation faster like the A* algorithm. http://en.wikipedia.org/wiki/A*

There are others, but these are tthe two most common.

Update from the discussion:

From our discussion I think going trough all permutations of the "must have nodes" B|L|I|D|G|K|J, starting from A and then going to A again would be an approach to solve it:

// Prepare a two dimensional array for the permutations
Node permutation[permutationCount][7];

// Fill it with all permutations
...

int cost[permutationCount];

for (int i = 0; i < permutationCount; ++i) {
    cost[i] =   dijkstraCost(nodeA,             permutation[i][0]) 
              + dijkstraCost(permutation[i][0], permutation[i][1])
              + dijkstraCost(permutation[i][1], permutation[i][2])
              + dijkstraCost(permutation[i][2], permutation[i][3])
              + dijkstraCost(permutation[i][3], permutation[i][4])
              + dijkstraCost(permutation[i][4], permutation[i][5])
              + dijkstraCost(permutation[i][5], permutation[i][6])
              + dijkstraCost(permutation[i][6], nodeA);
}

// Now Evaluate lowest cost and you have your shortest path(s)
....

I think that should work.

Answer 2

You are right it is a TSP, but what you need to do is too reduce the graph so it only contains nodes that are to be visited.

How to reduce the graph is left as an exercise for the reader ;-)