📄 netlen.asm
字号:
;网络中顶点间最短距离算法（利用邻接矩阵）。
;
;网络结构：
; A
; / | \
; 4 / | \ 7
; / | \
; B 6| C
; | \ 9 | 8 / |
; | \ | / |
; | \ | / |
; 8| D |5
; | / | \ 3 |
; | 5/ | \ |
; | / | \ |
; E 4| F
; \ | /
; \ | /
; 2 \ | / 9
; G
;
;从节点A出发的最短距离与路径：
; A
; / | \
; 4 / | \ 7
; / | \
; B=4 6| C=7
; |
; |
; |
; D=6
; / | \ 3
; 5/ | \
; / | \
; E=11 4| F=9
; |
; |
; |
; G=10
;
;从节点B出发的最短距离与路径：
; A=4
; / \
; 4 / \ 7
; / \
; B C=11
; | \ 9
; | \
; | \
; 8| D=9
; | \ 3
; | \
; | \
; E=8 F=12
; \
; \
; 2 \
; G=10
;
;从节点C出发的最短距离与路径：
; A=7
; / \
; 4 / \ 7
; / \
; B=11 C
; 8 / |
; / |
; / |
; D=8 |5
; / | |
; 5/ | |
; / | |
; E=13 4| F=5
; |
; |
; |
; G=12
;
;从节点D出发的最短距离与路径：
; A=6
; |
; |
; |
; B=9 6| C=8
; \ 9 | 8 /
; \ | /
; \ | /
; D
; / | \ 3
; 5/ | \
; / | \
; E=5 4| F=3
; |
; |
; |
; G=4
;
;
;从节点E出发的最短距离与路径：
; A=11
; |
; |
; |
; B=8 6| C=13
; | | 8 /
; | | /
; | | /
; 8| D=5
; | / \ 3
; | 5/ \
; | / \
; E F=8
; \
; \
; 2 \
; G=2
;
;
;从节点F出发的最短距离与路径：
; A=9
; |
; |
; |
; B=12 6| C=5
; \ 9 | |
; \ | |
; \ | |
; D=3 |5
; / | \ 3 |
; 5/ | \ |
; / | \ |
; E=8 4| F
; |
; |
; |
; G=7
;
;
;从节点G出发的最短距离与路径：
; A=10
; |
; |
; |
; B=10 6| C=12
; | | 8 /
; | | /
; | | /
; 8| D=4
; | | \ 3
; | | \
; | | \
; E=2 4| F=7
; \ |
; \ |
; 2 \ |
; G
;
NET EQU 20H ;网络存放的片外RAM页面（顶点总数不超过13）。
LEN EQU 0E0H ;距离数组起始地址。
POINT EQU 0F0H ;父指针数组起始地址。
N DATA 3EH ;顶点总数加一存放单元。
K DATA 3FH ;起始顶点编号存放单元。
ORG 0000H
LJMP TEST
ORG 100H
TEST: MOV DPTR,#NETDAT;将网络邻接矩阵拷贝到片外ＲＡＭ中。
MOV P2,#NET
MOV R0,#0
MOV R2,#80H
COPY: CLR A
MOVC A,@A+DPTR
MOVX @R0,A
INC DPTR
INC R0
DJNZ R2,COPY
MOV DPH,#NET;指向网络存放的片外RAM页面。
MOV DPL,#0
MOVX A,@DPTR ;读取网络顶点总数。
INC A
MOV N,A ;保存网络顶点总数。
MOV K,#1 ;以编号为１的顶点作为起点。
TEST1: LCALL MINLEN ;求解其它顶点到起点的最短距离。
INC K ;换一个顶点作为起点。
MOV A,K
CJNE A,N,TEST1
STOP: LJMP STOP
MINLEN: MOV DPH,#NET;指向网络存放的片外RAM页面。
MOV DPL,#0
MOVX A,@DPTR ;读取网络顶点总数。
MOV R7,A ;保存网络顶点总数。
MOV R6,A
CLEAR: MOV A,DPL ;指向访问标志数组（竖向分布）。
ADD A,#10H
MOV DPL,A
CLR A
MOVX @DPTR,A ;初始化访问标志。
DJNZ R6,CLEAR
MOV P2,#NET ;指向网络的存放页面。
MOV A,K ;读取起始顶点编号，作为生成树根节点编号。
MOV R2,A
SWAP A
MOV R1,A ;根节点标志单元。
MOV A,#1
MOVX @R1,A ;将根节点设置为已访问。
MOV R0,#LEN ;准备初始化距离数组。
MOV A,R7
MOV R6,A ;控制范围。
MINL: INC R1 ;调整指针。
INC R0
MOVX A,@R1 ;读取到根节点的距离。
MOVX @R0,A ;作为该顶点到生成树的初始距离。
DJNZ R6,MINL
MOV R0,#POINT;准备初始化父指针数组。
MOV A,R7 ;控制范围。
MOV R6,A
MOV A,R2 ;读取根节点的编号。
MINL1: INC R0
MOVX @R0,A ;作为其它顶点的父节点。
DJNZ R6,MINL1
MOV A,R2
ADD A,#POINT
MOV R0,A ;指向根节点自己的父节点单元。
MOV A,#0
MOVX @R0,A ;填入0，表示自己是根节点。
MOV A,R7
DEC A
MOV R3,A ;准备就其它顶点扩充到生成树中来。
MINL2: MOV R4,#0FFH;初始化距离最小值，准备寻找离起点最近的顶点。
MOV R5,#0 ;初始化距离最近顶点的编号。
MOV R0,#LEN+1;指向距离数组。
MOV R1,#10H ;指向标志数组。
MOV A,R7
MOV R6,A ;控制寻找范围。
MINL3: MOVX A,@R1 ;读取一个标志。
JNZ MINL4 ;该顶点已访问，跳过。
MOVX A,@R0 ;尚未访问，读取该顶点到起点的距离。
CLR C
SUBB A,R4 ;与当前最小值比较。
JNC MINL4 ;不是新的最小值。
MOVX A,@R0
MOV R4,A ;保存新的最小值。
MOV A,R0
ANL A,#0FH ;取新的最小值对应的顶点编号。
MOV R5,A ;保存新的最小值对应的顶点编号。
MINL4: INC R0 ;调整数组指针。
MOV A,R1 ;调整标志指针。
ADD A,#10H
MOV R1,A
DJNZ R6,MINL3;查完全部顶点。
MOV A,R5 ;读取找到的顶点编号。
SWAP A
MOV R0,A ;指向新顶点的标志单元。
MOV A,#1
MOVX @R0,A ;设置访问标志，该顶点进入生成树中。
INC R0 ;指向新顶点的邻接矩阵对应行。
MOV DPL,#LEN+1;指向距离数组。
MOV R1,#10H ;指向标志数组。
MOV A,R7
MOV R6,A ;控制调整范围，准备对距离数组进行调整。
MINL6: MOVX A,@R1 ;读取该顶点的访问标志。
JNZ MINL7 ;已访问，不需调整。
MOVX A,@R0 ;读取该顶点到新顶点的距离。
ADD A,R4 ;加上新顶点到起点的距离。
JC MINL7 ;太远（假设最大距离不超过255），不需调整。
MOV R2,A ;保存之。
MOVX A,@DPTR ;读取该顶点到起点的距离。
SETB C
SUBB A,R2 ;进行比较。
JC MINL7 ;通过新顶点到起点更远，不用调整。
MOV A,R2 ;取通过新顶点到起点的距离。
MOVX @DPTR,A ;作为该顶点到起点新的距离。
MOV A,R0 ;保存指针。
MOV R2,A
ANL A,#0FH
ADD A,#POINT
MOV R0,A ;指向该顶点的父节点编号存放单元。
MOV A,R5 ;以新顶点作为该顶点的父节点。
MOVX @R0,A ;
MOV A,R2 ;恢复指针。
MOV R0,A
MINL7: INC R0 ;调整指针。
INC DPTR
MOV A,R1
ADD A,#10H
MOV R1,A
DJNZ R6,MINL6;处理完距离数组的全部单元。
DJNZ R3,MINL2;继续查找生成树下一个准备吸收的顶点。
RET ;全部顶点均已进入生成树，算法结束。
;2000H: 07 41 42 43 44 45 46 47----顶点信息
;邻接矩阵 :
;2010H: 00 00 04 07 06 FF FF FF
;2020H: 00 04 00 FF 09 08 FF FF
;2030H: 00 07 FF 00 08 FF 05 FF
;2040H: 00 06 09 08 00 05 03 04
;2050H: 00 FF 08 FF 05 00 FF 02
;2060H: 00 FF FF 05 03 FF 00 09
;2070H: 00 FF FF FF 04 02 09 00
;
;20E0H: 00 00 00 00 00 00 00 00----距离数组
;20F0H: 00 00 00 00 00 00 00 00----父指针数组
NETDAT: DB 07H,41H,42H,43H
DB 44H,45H,46H,47H
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
DB 00H,00H,04H,07H
DB 06H,0FFH,0FFH,0FFH
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
DB 00H,04H,00H,0FFH
DB 09H,08H,0FFH,0FFH
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
DB 00H,07H,0FFH,00H
DB 08H,0FFH,05H,0FFH
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
DB 00H,06H,09H,08H
DB 00H,05H,03H,04H
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
DB 00H,0FFH,08H,0FFH
DB 05H,00H,0FFH,02H
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
DB 00H,0FFH,0FFH,05H
DB 03H,0FFH,00H,09H
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
DB 00H,0FFH,0FFH,0FFH
DB 04H,02H,09H,00H
DB 00H,00H,00H,00H
DB 00H,00H,00H,00H
END
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -