Go语言中Dijkstra算法的最短路径重建教程

type Vertex struct {
    Id      string
    Visited bool
    AdjEdge []*Edge
    Prev    *Vertex // 新增：指向最短路径上的前一个顶点
}

if D[edge.Destination] > D[edge.Source]+edge.Weight {
    D[edge.Destination] = D[edge.Source] + edge.Weight
    // ... 在这里添加记录前驱的逻辑
}

const MAXWEIGHT = 1000000

type MinDistanceFromSource map[*Vertex]int

// Dijks 函数保持不变，或根据需要初始化所有Prev为nil
func (G *Graph) Dijks(StartSource, TargetSource *Vertex) MinDistanceFromSource {
  D := make(MinDistanceFromSource)
  for _, vertex := range G.VertexArray {
    D[vertex] = MAXWEIGHT
    vertex.Prev = nil // 初始化Prev指针
  }
  D[StartSource] = 0
  StartSource.Prev = nil // 源点没有前驱

  // 初始边的处理，同样需要设置Prev
  for edge := range StartSource.GetAdEdg() {
    if D[edge.Destination] > edge.Weight { // 确保是更短路径才更新
        D[edge.Destination] = edge.Weight
        edge.Destination.Prev = StartSource // 设置前驱
    }
  }
  CalculateD(StartSource, TargetSource, D) // 递归调用可能需要调整为迭代
  return D
}

// CalculateD 函数应调整为迭代式，这里仅展示关键的更新逻辑
// 原始的递归实现可能存在栈溢出风险，且不完全符合Dijkstra的典型迭代结构。
// 假设这是在Dijkstra主循环内部的松弛操作
func CalculateD(currentVertex *Vertex, D MinDistanceFromSource) {
    // 遍历当前顶点的所有邻接边
    for edge := range currentVertex.GetAdEdg() {
        // 如果通过当前顶点到达目标顶点的路径更短
        if D[edge.Destination] > D[currentVertex]+edge.Weight {
            D[edge.Destination] = D[currentVertex] + edge.Weight
            edge.Destination.Prev = currentVertex // 关键：更新前驱指针
        }
    }
    // 注意：一个完整的Dijkstra算法会有一个优先队列来选择下一个要处理的顶点
    // 这里的CalculateD片段仅展示了更新前驱的核心逻辑
}

// PrintPath 从目标顶点回溯打印路径
func PrintPath(target *Vertex) {
    if target == nil {
        fmt.Println("目标顶点为空，无法打印路径。")
        return
    }

    path := []string{}
    current := target

    // 从目标顶点开始，反向回溯到源点
    for current != nil {
        path = append(path, current.Id)
        current = current.Prev
    }

    // 路径是逆序的，需要反转
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }

    // 打印路径
    fmt.Print("最短路径: ")
    for i, id := range path {
        fmt.Print(id)
        if i < len(path)-1 {
            fmt.Print(" -> ")
        }
    }
    fmt.Println()
}

// 假设 distmap1 是 Dijks 返回的结果，TargetSource 是你的目标顶点
// G.Dijks(StartSource, TargetSource) 应该返回一个包含Prev指针的Vertex结构
// ... 运行Dijkstra算法 ...

// 遍历所有顶点，打印它们的距离和路径
for vertex, distance := range distmap1 {
    fmt.Printf("从源点到 %s 的最短距离: %d\n", vertex.Id, distance)
    if distance != MAXWEIGHT { // 如果可达
        PrintPath(vertex)
    } else {
        fmt.Printf("从源点到 %s 不可达\n", vertex.Id)
    }
    fmt.Println("---")
}