Question

网络理论的最短路径问题

Answer 1

一般提法是：寻找网络中两点间的最短路径晌扒茄,即寻找连接这两点的边的总权数(可以是距离、时间、费用等)为最小的通路。图4为最短路径问题的一此瞎个例子。最短路径问题有两种算法。戴克斯特拉法　1959年提出。其计算方法是：从始点vs,标以零值,并记在vs旁的方括号内。然后依节点序号顺序找出到达各点的最短距离,并说明来自何方,例如在节点v3处标上【v2,4】,即表宴察示来自节点v2，距离累计为4。戴克斯特拉法可以通过编制计算程序,在计算机上运算。