c - 寻找一种算法来找到最短路径

Question

基本上我有一个包含 12 个节点(代表城市)和 13 条边(代表路线)的图。

现在让我们说(随机地)我有一个访问 n 个节点的计划，从特定的节点 (A) 出发。所以 ( having N <= (12-1) ) 然后来到起点。

对于我一直在寻找的内容，它看起来几乎像 Traveling Salesman Problem但不同的是，在我的推销员中不一定需要访问所有节点。

我在寻找什么算法？

编辑

显然这不会成为 TSP，因为 TSP 表示图必须闭合并且我们仅遍历每个城市(节点)一次。在我的例子中，如果它能缩短路线，它可以多次穿过一个城市。

我正在寻找的更多示例:

例子一:

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

例子二:

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

规则:

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

请记住，这是针对 C 语言的项目，因此这只是预编码研究。

Answer 1

有很多算法可以做到这一点。口号是寻路。

一开始学习的最佳算法是古老的 Dijkstra http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

然后对于较大的图(不是迷宫)，您可能需要一种具有某些方向启发式算法的算法，以便像 A* 算法一样更快地进行评估。 http://en.wikipedia.org/wiki/A *

还有其他的，但这是最常见的两种。

讨论更新:

根据我们的讨论，我认为遍历“必须有节点”B|L|I|D|G|K|J 的所有排列，从 A 开始然后再次转到 A 将是解决它的一种方法:

// 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)
....

我认为这应该可行。