- 1 -
一、设计思想
下面给出的是迪杰斯特拉算法实现的设计思想。
(1)首先建立一个二维数组 cost[][]来保存节点之间的权值，如果两节点之间不存在连线，
则设置权值为 max，节点到自身的权值也设置为 max，通过数组对权值进行调用。首先选
择起点 v，比较它与其它各点是否直接相连，若直接相连，则用 dist[i]保存这两点的权值。
之后进行横向比较，找到所有路径中最短的一个赋给 wm。之后以找到的最短路径的节点
为起点，比较从原点出发通过该节点再到其他节点的距离是否比之前找到的从原点出发到
此节点的路径距离短。如果短，则把此路径赋给此节点；如果不短，则继续保持其原有路
径。重复此步，直到最后找到所有点的最短路径为止。在循环过程中，已经找到最短路径
的节点用 s[i]=1 表示，则在之后的寻路径中不再寻找该节点的最短路径。路径通过 path[]数
组保存，如 path[4]=3，则表示节点 4 的前一个节点为 3，之后寻找 path[3]的前一个节点，
知道找到原点为止，设原点 path[v]=-1。
(2)通过 path[]输出最短路径的文字显示。首先建立一个 0 到 4 的循环结构，使 i 依次等
于 0 到 4，之后通过 dist[i]输出原点到 i 的最短距离。之后通过 path[i]寻找到到节点 i 的路径。
在这一步先用 temp=path[i]，之后依次赋值 temp=path[temp]，依次输出经过的节点。最后
回到起始点 path[v]，之前将-1 赋给 path[v]，所以当 path[temp]=-1 的时候结束输出，于是路
径输出完毕。
(3)在图中画出原点到各节点的最短路径。在这里用了一个数组 m[]，将在每次循环中
找到的 j 的值依次放在数组 m 中。这样在画图过程中就会按照找到的顺序依次连线。这里
运用了一个公式 s1=a*10+path[a]。这个公式巧妙的将原本倒着找到的路径正着画出。比如
在第一次中，j=1，这时 a=1，path[1]=0。这时 s1 的值为 10，则通过 switch(s1)，便会调用
case 01:case 10:line(350,150,150,250);。这时会画出 0 到 1 的线。由于 a 是按照在迪杰斯特拉
中找到 j 的顺序依次赋值的，因此，输出的线也会是按照权重递增的顺序画出来的。由于
原点已经被排除在要寻找的节点之外，所以循环的次数也就定义为 4 次，即 i=0;i<n-1;i+
+。当这个循环结束之后，所有的路径就用红色线条输出完毕，在图中就可以看到原点到
各个节点的最短路径图。
二、算法流程图
下面给出的图 1 为迪杰斯特拉算法的实现的流程图。
