验证FSM中从“开始”状态到“结束”状态的每个状态的可达性

Question

我从一个有N个状态的有限状态机开始（即状态图上的N个顶点）。 其中一个状态是“开始”状态，一个状态是“结束”状态。在

我想做的是-

1. 检查是否可以从“开始”状态访问其他N-2状态
2. 检查是否可以从N-2个状态中的每个状态到达“结束”状态

实现这一目标的最佳算法是什么？
另外，是否有任何Python模块可以以最小的工作量完成这个验证（比如仅仅是一个函数调用）？在

Answer 1

我找到了这个Python模块Networkx，它对我帮助很大。
This(networkx.最短路径)特别是我使用的函数。在

贴在对我有用的溶液下面。在

import networkx as nx

G = nx.DiGraph()
G.add_nodes_from(["Start", "a", "b", "c", "End"])
G.add_edges_from([("Start", "a"), ("Start", "c"), ("a", "b"), ("b", "a"), ("c", "End")])

total_num_nodes = G.number_of_nodes()

if len(nx.shortest_path(G, source="Start")) < total_num_nodes:
    print "\nThis FSM has inaccessible states"
else:
    print "\nAll nodes reachable from 'Start'"

H = G.reverse()
if len(nx.shortest_path(H, source="End")) < total_num_nodes:
    print "\nThis FSM has dead-end states"
else:
    print "\nAll nodes have a path to reach the 'End' state"