c-求图中节点之间的最短路径

Question

我有一个状态机，看起来像这样：

G--H
/
A--B--C--D--E--F

我想要一个函数goToState(target)，它将目标状态作为输入参数，然后该函数将执行从当前状态开始的所有转换，直到达到目标状态。

例如，假设当前状态为B，我们称之为goToState(F)。然后，该功能将进行以下状态转换B->C、 C->D、 D->E、 E->F.

转换是双向工作的，所以如果当前状态是F并且我们调用goToState(G)，那么函数将执行F->E、 E->D、 D->G.

如果我们有一个线性状态机(例如，没有分支G-H)，那么我只需要按照法定顺序为每个转换执行一组函数，然后找到当前状态的索引和目标状态的索引，并在for循环中调用这两个索引之间的所有转换函数。

然而，现在我有了一个分支，这种方法就不起作用了。对法律转换进行编码并实现基于C中的目标状态以正确顺序执行它们的函数的最有效方法是什么？

编辑：正如其他一些用户很好地指出的那样，我正在寻找某种路径查找算法，它可以找到两种状态之间的最短路径。我只是在最初的帖子中找不到合适的词语来恰当地表达它。我需要一种最简单的路径查找算法，它适用于如上所示的状态图。状态图永远不会变得比这更复杂，所以算法也不需要覆盖任何其他场景。

第2版：更新了标题以更好地描述问题。你的评论帮助我找到了正确的术语，这样我就可以在网上搜索解决方案。

Answer 1

我在GeeksforGeeks网站上找到了答案：https://www.geeksforgeeks.org/shortest-path-unweighted-graph/

这是广度优先搜索算法的修改版本，正是我所需要的！

感谢大家的回答和评论。他们帮助我找到了正确的术语，以便在网上搜索正确的解决方案。

Answer 2

您可以将状态建模为一个结构数组，每个结构都包含一个用于转换的函数指针和一个可能的目标状态数组。

然后，创建一个获取当前状态和目标状态的函数，并使其在可能的状态列表中循环。如果其中一个与目的地匹配，请将其放在一个空的状态列表的开头，然后返回该列表。如果没有，则遍历每个可能的中间状态，直到其中一个返回非空列表，并将当前状态添加到列表的前面。

递归函数返回后，您可以在运行转换的列表中进行迭代。

#include <stdio.h>
#include <stdlib.h>
typedef void (*func)(void);    // modify as needed
typedef enum { NONE=-1, A, B, C, D, E, F, G, H, MAX_STATES } states;
struct transitions {
func transition;
states slist[MAX_STATES];
};
struct tlist {
struct transitions *trans;
struct tlist *next;
};
void trans_a(void) { printf("transition An"); }
void trans_b(void) { printf("transition Bn"); }
void trans_c(void) { printf("transition Cn"); }
void trans_d(void) { printf("transition Dn"); }
void trans_e(void) { printf("transition En"); }
void trans_f(void) { printf("transition Fn"); }
void trans_g(void) { printf("transition Gn"); }
void trans_h(void) { printf("transition Hn"); }
struct transitions transitions[] = {
{ trans_a, { B, NONE } },
{ trans_b, { A, C, NONE } },
{ trans_c, { B, D, NONE } },
{ trans_d, { C, G, E, NONE } },
{ trans_e, { D, F, NONE } },
{ trans_f, { E, NONE } },
{ trans_g, { D, H, NONE } },
{ trans_h, { G, NONE } }
};
struct tlist *getStates(states prev, states start, states end)
{
int i;
for (i = 0; transitions[start].slist[i] != NONE; i++) {
if (transitions[start].slist[i] == prev) continue;
if (transitions[start].slist[i] == end) {
struct tlist *entry = malloc(sizeof *entry);
entry->trans = transitions + start;
entry->next = NULL;
return entry;
}
struct tlist *list = getStates(start, transitions[start].slist[i], end);
if (list) {
struct tlist *entry = malloc(sizeof *entry);
entry->trans = transitions + start;
entry->next = list;
return entry;
}
}
return NULL;
}
void runStates(states start, states end)
{
printf("from %d to %dn", start, end);
struct tlist *list = getStates(NONE,start,end);
while (list) {
struct tlist *tmp = list;
list->trans->transition();
list = list->next;
free(tmp);
}
printf("n");
}
int main()
{
runStates(A,H);
runStates(A,E);
runStates(E,A);
runStates(F,H);
return 0;
}

输出：

from 0 to 7
transition A
transition B
transition C
transition D
transition G
from 0 to 4
transition A
transition B
transition C
transition D
from 4 to 0
transition E
transition D
transition C
transition B
from 5 to 7
transition F
transition E
transition D
transition G

Answer 3

我认为已经公布的答案足以回答这个问题，但我想补充一点，这是一个在理论计算的抽象数学领域研究的经典问题。描述你所要求的计算的数学模型被称为有限状态机。FSM是一种抽象机器，它包含(不需要深入研究数学术语或符号)：

1. 一种输入语言，在您的情况下，它是您传递给函数的任何语言，以找出您的程序应该转换到哪个状态(在我的示例中为"target")
2. 一组状态，在您的情况下是A、B、C、D、E、F、G和H
3. 初始状态，它是程序启动的上述状态集中的任何一个
4. 一个转换函数，它告诉每个状态在输入语言中给定任何输入的情况下从任何给定的状态到哪里(在我的例子中是函数"transtition")
5. 一组最终状态，它要么是空的，要么是状态集的子集

问题的关键是关于第4项，转换函数。FSM的转换函数的C实现可能符合您的需求，它可能看起来像这样：

//Model states as integers from 0-7 plus an extra invalid state for error handling
enum state{A, B, C, D, E, F, G, H, invalid};
enum state transition(enum state current, enum state target){

if(target < A || target > H || current < A || current > H)
return invalid;
else if(target == current)
return current;
switch(current){
case A:
return B;
case B: //B and C have combinable transition behavior
case C:
if(target > current)
return current + 1;
else
return current - 1;
case D:
if(target < D)
return C;
else if(target > F)
return G;
else
return E;
case E:
if(target < E)
return D;
else
return F;
case F:
return E;
case G:
if(target < G)
return D;
else
return H;
case H:
return G;
//Edge-cases have been managed so no need for default case
}
}

然后在中，您可以像这样实现goToState()：

int goToState(enum state current,enum state target){
while(current != target && current != invalid){
current = transtition(current, target);
handle(current);  //Do whatever must be done for whatever state we are in along the way
}
if(current == invalid)
return -1; //Error code
else
return 0;
}

Answer 4

无论状态机如何，您都希望避免"stateghetti"；，这就是当每个状态就下一步执行哪个状态做出多个局部决定时会发生的情况。

相反，让每个状态返回一个结果代码。不管怎样，您仍然可以拥有一个函数指针数组。然后在程序的顶层，按照以下伪代码的行写一些东西：

while(...)
{
result = state_machine[current_state]();
current_state = evaluate(current_state, result);
}

函数evaluate()是代码中允许状态转换的唯一位置。可选地，它可以兼作顶级错误处理程序。

然后只需在这个函数中编码所有需要的依赖项：

...
if(state==C && result==OK)
return D;
if(state==D)
{
if(result==OK)
return E;
else
return G;
}
...