使用 Go 实现 Dijkstra 算法

运维开发王义杰

发布于 2023-10-23 20:19:29

2390

发布于 2023-10-23 20:19:29

文章被收录于专栏：运维开发王义杰运维开发王义杰

Dijkstra 算法是计算图中两个顶点之间的最短路径的一个经典算法。这篇文章我们将深入探讨如何使用 Go 语言实现它，并提供详尽的代码。

1. 算法简介

Dijkstra 算法是由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出的。这个算法可以找到从起始点到图中所有其他点的最短路径。算法的主要思想是：每次从未处理的顶点中选取一个与起始点距离最短的顶点，然后更新所有与该顶点相邻的顶点的最短路径。

2. 算法流程

初始化：将起始点的距离设为 0，其他所有点的距离设为无穷大。
从未处理的顶点中选取一个与起始点距离最短的顶点。
更新所有与该顶点相邻的顶点的最短路径。
重复第2步和第3步，直到所有的顶点都被处理过。

3. Go 代码实现


type Graph struct {
  vertices []*Vertex
}

type Vertex struct {
  key      int
  adjacent []*Vertex
  weight   []int
  dist     int
  previous *Vertex
}

func NewVertex(key int) *Vertex {
  return &Vertex{
    key: key,
  }
}

func (g *Graph) AddVertex(key int) {
  if contains(g.vertices, key) {
    return
  }
  g.vertices = append(g.vertices, NewVertex(key))
}

func (g *Graph) AddEdge(from, to, weight int) {
  fromVertex := g.getVertex(from)
  toVertex := g.getVertex(to)
  fromVertex.adjacent = append(fromVertex.adjacent, toVertex)
  fromVertex.weight = append(fromVertex.weight, weight)
}

func (g *Graph) getVertex(key int) *Vertex {
  for i := 0; i < len(g.vertices); i++ {
    if g.vertices[i].key == key {
      return g.vertices[i]
    }
  }
  return nil
}

func contains(s []*Vertex, key int) bool {
  for _, v := range s {
    if key == v.key {
      return true
    }
  }
  return false
}

func Dijkstra(source *Vertex) {
  source.dist = 0
  var queue []*Vertex
  for _, vertex := range g.vertices {
    queue = append(queue, vertex)
  }

  for len(queue) != 0 {
    // TODO: 从队列中找到最小的距离顶点
    // TODO: 更新与该顶点相邻的所有顶点的距离
  }
}