MIPS32汇编DFS单源最短路径代码运行异常，求排查修复

问题背景 #

我用DFS实现了单源最短路径的C代码，转写为MIPS32汇编后能正常汇编运行，但输出结果不正确。怀疑递归调用dfs函数时存在问题，尝试过程序分步调试但仍未理清问题所在；也试过用Godbolt转换代码，但平台没有MIPS32选项，加上自身对汇编不熟悉，无法理解转换后的其他汇编代码逻辑。

相关代码 #

原始C代码 #

#include <stdio.h>
#include <limits.h>

#define V 5

void dfs(int graph[V][V], int src, int dist[], int visited[]) {
    visited[src] = 1;
    for (int i = 0; i < V; i++) {
        if (graph[src][i] != 0 && !visited[i]) {
            if (dist[i] > dist[src] + graph[src][i]) {
                dist[i] = dist[src] + graph[src][i];
            }
            dfs(graph, i, dist, visited);
            visited[i] = 0; // 回溯
        }
    }
}

void init_dist(int dist[], int src) {
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
    }
    dist[src] = 0;
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0},
        {4, 0, 8, 0, 0},
        {0, 8, 0, 7, 0},
        {0, 0, 7, 0, 9},
        {0, 0, 0, 9, 0}
    };
    int dist[V], visited[V] = {0};
    init_dist(dist, 0);
    dfs(graph, 0, dist, visited);
    
    printf("最短路径距离：\n");
    for (int i = 0; i < V; i++) {
        printf("从0到%d：%d\n", i, dist[i]);
    }
    return 0;
}

我的MIPS32汇编实现代码 #

.data
graph:      .word 0,4,0,0,0
            .word 4,0,8,0,0
            .word 0,8,0,7,0
            .word 0,0,7,0,9
            .word 0,0,0,9,0
dist:       .space 20
visited:    .space 20
msg:        .asciiz "最短路径距离：\n从0到%d：%d\n"
V:          .word 5
INT_MAX:    .word 0x7FFFFFFF

.text
.globl main

main:
    # 初始化dist数组
    la $a0, dist
    li $a1, 0
    jal init_dist
    
    # 初始化visited为0
    la $t0, visited
    li $t1, 0
    li $t2, 5
init_visited_loop:
    sw $t1, ($t0)
    addi $t0, $t0, 4
    addi $t2, $t2, -1
    bgtz $t2, init_visited_loop
    
    # 调用dfs
    la $a0, graph
    li $a1, 0
    la $a2, dist
    la $a3, visited
    jal dfs
    
    # 输出结果
    la $t0, dist
    li $t1, 0
    li $t2, 5
    la $a0, msg
print_loop:
    lw $t3, ($t0)
    move $a1, $t1
    move $a2, $t3
    jal printf
    addi $t0, $t0, 4
    addi $t1, $t1, 1
    addi $t2, $t2, -1
    bgtz $t2, print_loop
    
    li $v0, 10
    syscall

init_dist:
    la $t0, INT_MAX
    lw $t1, ($t0)
    la $t2, V
    lw $t3, ($t2)
    move $t4, $a0       # dist地址
    li $t5, 0
init_dist_loop:
    sw $t1, ($t4)
    addi $t4, $t4, 4
    addi $t5, $t5, 1
    bne $t5, $t3, init_dist_loop
    # 设置src的dist为0
    sll $t6, $a1, 2
    add $t6, $a0, $t6
    sw $zero, ($t6)
    jr $ra

dfs:
    # 保存寄存器到栈
    addi $sp, $sp, -20
    sw $ra, 16($sp)
    sw $s0, 12($sp)
    sw $s1, 8($sp)
    sw $s2, 4($sp)
    sw $s3, 0($sp)
    
    move $s0, $a0       # graph地址
    move $s1, $a1       # src
    move $s2, $a2       # dist地址
    move $s3, $a3       # visited地址
    
    # 标记visited[src] = 1
    sll $t0, $s1, 2
    add $t0, $s3, $t0
    li $t1, 1
    sw $t1, ($t0)
    
    # 循环i从0到V-1
    li $t2, 0
    la $t3, V
    lw $t4, ($t3)
dfs_loop:
    bge $t2, $t4, dfs_exit
    
    # 检查graph[src][i] != 0
    sll $t5, $s1, 2
    mul $t5, $t5, $t4   # src * V *4
    sll $t6, $t2, 2     # i*4
    add $t5, $t5, $t6
    add $t5, $t5, $s0
    lw $t7, ($t5)
    beqz $t7, dfs_loop_next
    
    # 检查!visited[i]
    sll $t8, $t2, 2
    add $t8, $t8, $s3
    lw $t9, ($t8)
    bnez $t9, dfs_loop_next
    
    # 检查dist[i] > dist[src] + graph[src][i]
    sll $t8, $t2, 2
    add $t8, $t8, $s2
    lw $t9, ($t8)       # dist[i]
    
    sll $t0, $s1, 2
    add $t0, $t0, $s2
    lw $t1, ($t0)       # dist[src]
    add $t1, $t1, $t7   # dist[src] + graph[src][i]
    
    ble $t9, $t1, dfs_call_dfs
    
    # 更新dist[i]
    sw $t1, ($t8)
    
dfs_call_dfs:
    # 递归调用dfs(graph, i, dist, visited)
    move $a0, $s0
    move $a1, $t2
    move $a2, $s2
    move $a3, $s3
    jal dfs
    
    # 回溯：visited[i] = 0
    sll $t8, $t2, 2
    add $t8, $t8, $s3
    sw $zero, ($t8)
    
dfs_loop_next:
    addi $t2, $t2, 1
    j dfs_loop

dfs_exit:
    # 恢复寄存器
    lw $s3, 0($sp)
    lw $s2, 4($sp)
    lw $s1, 8($sp)
    lw $s0, 12($sp)
    lw $ra, 16($sp)
    addi $sp, $sp, 20
    jr $ra

printf:
    # 简单的printf封装
    li $v0, 4
    syscall
    li $v0, 1
    move $a0, $a1
    syscall
    li $v0, 11
    li $a0, ':'
    syscall
    li $v0, 1
    move $a0, $a2
    syscall
    li $v0, 11
    li $a0, '\n'
    syscall
    jr $ra

Godbolt转换的x86汇编代码 #

dfs:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 32
        mov     QWORD PTR [rbp-24], rdi
        mov     DWORD PTR [rbp-28], esi
        mov     QWORD PTR [rbp-16], rdx
        mov     QWORD PTR [rbp-8], rcx
        mov     eax, DWORD PTR [rbp-28]
        mov     rdx, QWORD PTR [rbp-8]
        mov     eax, eax
        mov     DWORD PTR [rdx+rax*4], 1
        mov     DWORD PTR [rbp-4], 0
.L3:
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 4
        jge     .L2
        mov     eax, DWORD PTR [rbp-28]
        mov     ecx, eax
        imul    ecx, ecx, 5
        mov     eax, DWORD PTR [rbp-4]
        lea     rdx, [rcx+rax*4]
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        mov     eax, DWORD PTR [rax]
        test    eax, eax
        je      .L4
        mov     eax, DWORD PTR [rbp-4]
        mov     rdx, QWORD PTR [rbp-8]
        mov     eax, DWORD PTR [rdx+rax*4]
        test    eax, eax
        jne     .L4
        mov     eax, DWORD PTR [rbp-4]
        mov     rdx, QWORD PTR [rbp-16]
        mov     eax, DWORD PTR [rdx+rax*4]
        mov     ecx, eax
        mov     eax, DWORD PTR [rbp-28]
        mov     rdx, QWORD PTR [rbp-16]
        mov     eax, DWORD PTR [rdx+rax*4]
        mov     edx, DWORD PTR [rbp-4]
        mov     rsi, QWORD PTR [rbp-24]
        mov     edx, DWORD PTR [rsi+rdx*4+rax*20]
        add     eax, edx
        cmp     ecx, eax
        jle     .L5
        mov     eax, DWORD PTR [rbp-4]
        mov     rdx, QWORD PTR [rbp-16]
        mov     DWORD PTR [rdx+rax*4], eax
.L5:
        mov     rcx, QWORD PTR [rbp-8]
        mov     rdx, QWORD PTR [rbp-16]
        mov     esi, DWORD PTR [rbp-4]
        mov     rdi, QWORD PTR [rbp-24]
        call    dfs
        mov     eax, DWORD PTR [rbp-4]
        mov     rdx, QWORD PTR [rbp-8]
        mov     DWORD PTR [rdx+rax*4], 0
.L4:
        add     DWORD PTR [rbp-4], 1
        jmp     .L3
.L2:
        nop
        leave
        ret

错误分析与修复 #

1. 整数溢出问题（核心错误） #

C代码中dist初始化为INT_MAX，当dist[src]为INT_MAX时，执行dist[src] + graph[src][i]会触发整数溢出，MIPS中会产生错误的负数或乱码值，导致dist[i]的更新逻辑完全错误。

修复代码：在计算距离和之前，添加dist[src]是否为INT_MAX的检查，跳过无效更新：

# 替换dfs函数中距离计算的代码段
sll $t0, $s1, 2
add $t0, $t0, $s2
lw $t1, ($t0)       # dist[src]
# 新增：检查dist[src]是否为INT_MAX
la $t0, INT_MAX
lw $t0, ($t0)
beq $t1, $t0, dfs_call_dfs  # 若为INT_MAX，直接跳转到递归调用
# 继续原逻辑
add $t1, $t1, $t7   # dist[src] + graph[src][i]

2. 自定义printf输出逻辑错误 #

原汇编中的printf函数未正确处理格式化字符串，输出内容混乱，容易误导判断。改用拆分式系统调用实现正确输出：

修改.data段：

msg_header: .asciiz "最短路径距离：\n"
prefix:     .asciiz "从0到"
colon:      .asciiz "："
newline:    .asciiz "\n"

修改main中的输出逻辑：

# 替换原print_loop代码
la $a0, msg_header
li $v0, 4
syscall

la $t0, dist
li $t1, 0
la $t2, V
lw $t3, ($t2)
print_loop:
    bge $t1, $t3, print_end
    
    # 输出前缀
    la $a0, prefix
    li $v0,4
    syscall
    # 输出节点编号
    move $a0, $t1
    li $v0,1
    syscall
    # 输出冒号
    la $a0, colon
    li $v0,4
    syscall
    # 输出距离
    lw $a0, ($t0)
    li $v0,1
    syscall
    # 输出换行
    la $a0, newline
    li $v0,4
    syscall
    
    addi $t0, $t0,4
    addi $t1, $t1,1
    j print_loop
print_end:

3. 递归栈帧验证 #

你的dfs函数栈帧操作（保存/恢复$ra和$s0-$s3）逻辑正确，栈空间分配足够，递归返回地址不会混乱，这部分无需修改。

内容的提问来源于stack exchange，提问作者PhiLO