超难.................(能做出来智商起码150)

工藤￥新一

无项图最短路径是不是编程？

SP(Shortest Path，最短路径)问题是编程中最常见的问题之一，下面介绍2个计算最短路径的算法。
输入文件格式：
第一行：n，代表端点数
第2到n+1行：邻接矩阵

一、Floyd-Warshall算法
　　该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。即：
　　Dij=min(Dij,Dik+Dkj，……)，1<=k<=5。
　这样，我所就找到了一个类似动态规划的表达式，只不过这里我们不把它当作动态规划去处理，而是做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到A到E的最短路径

程序如下：
CLS
CONST max = 200
CONST maxn = 30
DIM SHARED n, s, f
DIM SHARED map(maxn, maxn)
CALL init
CALL floyd
CALL show

SUB floyd
FOR k = 1 TO n
FOR i = 1 TO n
FOR j = 1 TO n
   IF map(i, j) > map(i, k) + map(k, j) THEN
      map(i, j) = map(i, k) + map(k, j)
   END IF
NEXT j, i, k
END SUB

SUB init
INPUT "File Name:", fin$
OPEN fin$ FOR INPUT AS #1
INPUT #1, n
FOR i = 1 TO n
FOR j = 1 TO n
  INPUT #1, map(i, j)
NEXT j, i
FOR i = 1 TO n
FOR j = 1 TO n
  IF map(i, j) = 0 THEN map(i, j) = max
NEXT j, i
INPUT "Starting Point:", s
INPUT "Finishing Point:", f
END SUB

SUB show
PRINT "The Shortest Length From "; s; " to "; f; " is "; , map(s, f)
END SUB

这个算法是常用的算法之一，复杂度为O(n^3)


二、Dijkstra算法（类似标号法，一般不作区分）
所谓标号法的基本思想是从起点s出发，逐步地向外探寻最短路。在执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从s到该点的最短路的权（称为P标号），或者表示这个权的上界（称为T标号），具体做法是每扩展一步，就将一个具T标号的点改具P标号的点，从而使有向图D中具P标号的顶点数增多一个。如此一步步执行下去，就可求出从s到各点的最短路。
程序如下：
CLS
CONST maxn = 50
DIM SHARED n, s, f
DIM SHARED map(maxn, maxn), dis(maxn), mark(maxn)      
'mark记录是否已被标号，dis存s到各点的距离。
CALL init        '初始化
CALL dijkstra      '主过程
CALL show       '输出
END

SUB dijkstra
DO
  bv = 0
  FOR i = 1 TO n
    IF mark(i) THEN
      FOR j = 1 TO n
        IF mark(j) = 0 AND map(i, j) THEN
          IF bv = 0 OR dis(i) + map(i, j) < bv THEN
            bv = dis(i) + map(i, j)
            bn = j
          END IF
        END IF
      NEXT j
    END IF
  NEXT i
  IF bv > 0 THEN
    mark(bn) = 1
    dis(bn) = bv
  END IF
LOOP UNTIL bv = 0
END SUB

SUB init
INPUT "File Name:", fin$
OPEN fin$ FOR INPUT AS #1
INPUT #1, n
FOR i = 1 TO n
FOR j = 1 TO n
  INPUT #1, map(i, j)
NEXT j
NEXT i
CLOSE
INPUT "Starting Point:", s
INPUT "Finishing Point:", f
mark(s) = 1
END SUB

SUB show
PRINT "The Shortest Length From "; s; " to "; f; " is "; dis(f)
END SUB