Dijkstra算法 - 元素码农

发布时间: 2025-03-21 19:21

↑

# Dijkstra算法

Dijkstra算法是一种用于计算带权有向图中单源最短路径的经典算法。本文将详细介绍Dijkstra算法的原理、实现和应用。

## 基本概念

### 最短路径问题

在带权图中，从一个顶点到另一个顶点可能存在多条路径，每条路径的长度是路径上所有边的权重之和。最短路径问题就是要找出从源顶点到目标顶点的最小权重路径。

### 算法适用条件

1. 有向图或无向图
2. 边权重为非负数
3. 图可以是稠密图或稀疏图

## 算法原理

### 核心思想

Dijkstra算法使用贪心策略，维护一个已知最短路径的顶点集合S和一个候选顶点集合Q。每次从Q中选择到源点距离最小的顶点u加入S，然后更新u的所有邻接顶点的距离。

### 算法步骤

1. 初始化：
   - 源点距离设为0
   - 其他顶点距离设为无穷大
   - 所有顶点加入候选集Q

2. 主循环：
   - 从Q中选择距离最小的顶点u
   - 将u从Q中移除加入S
   - 更新u的所有邻接顶点的距离

3. 重复步骤2直到Q为空

## 代码实现

### 基本实现

```go
type Edge struct {
    to     int
    weight int
}

type Graph struct {
    vertices int
    adj      [][]Edge
}

func NewGraph(v int) *Graph {
    return &Graph{
        vertices: v,
        adj:      make([][]Edge, v),
    }
}

func (g *Graph) AddEdge(from, to, weight int) {
    g.adj[from] = append(g.adj[from], Edge{to: to, weight: weight})
}

func (g *Graph) Dijkstra(source int) []int {
    // 初始化距离数组和访问标记
    dist := make([]int, g.vertices)
    visited := make([]bool, g.vertices)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[source] = 0

// 主循环
    for i := 0; i < g.vertices; i++ {
        // 找到未访问的最小距离顶点
        u := -1
        minDist := math.MaxInt32
        for v := 0; v < g.vertices; v++ {
            if !visited[v] && dist[v] < minDist {
                u = v
                minDist = dist[v]
            }
        }
        if u == -1 {
            break
        }

// 标记顶点为已访问
        visited[u] = true

// 更新邻接顶点的距离
        for _, edge := range g.adj[u] {
            v := edge.to
            if !visited[v] {
                newDist := dist[u] + edge.weight
                if newDist < dist[v] {
                    dist[v] = newDist
                }
            }
        }
    }

return dist
}
```

### 优先队列优化

```go
type Item struct {
    vertex   int
    distance int
    index    int
}

type PriorityQueue []*Item

// 实现heap.Interface所需的方法
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].distance < pq[j].distance }
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil
    item.index = -1
    *pq = old[0 : n-1]
    return item
}

func (g *Graph) DijkstraWithPQ(source int) []int {
    dist := make([]int, g.vertices)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[source] = 0

// 创建优先队列
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    heap.Push(&pq, &Item{vertex: source, distance: 0})

for pq.Len() > 0 {
        // 取出最小距离顶点
        u := heap.Pop(&pq).(*Item)

// 如果取出的距离大于已知距离，跳过
        if u.distance > dist[u.vertex] {
            continue
        }

// 更新邻接顶点的距离
        for _, edge := range g.adj[u.vertex] {
            v := edge.to
            newDist := dist[u.vertex] + edge.weight
            if newDist < dist[v] {
                dist[v] = newDist
                heap.Push(&pq, &Item{vertex: v, distance: newDist})
            }
        }
    }

return dist
}
```

## 应用示例

### 导航系统

```go
type Location struct {
    id   int
    name string
    x, y float64
}

type NavigationSystem struct {
    locations []Location
    graph     *Graph
}

func NewNavigationSystem(locations []Location) *NavigationSystem {
    n := len(locations)
    ns := &NavigationSystem{
        locations: locations,
        graph:     NewGraph(n),
    }
    
    // 根据位置构建图
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j {
                // 计算两点间距离作为权重
                dx := locations[i].x - locations[j].x
                dy := locations[i].y - locations[j].y
                distance := int(math.Sqrt(dx*dx + dy*dy))
                ns.graph.AddEdge(i, j, distance)
            }
        }
    }
    
    return ns
}

func (ns *NavigationSystem) FindShortestPath(from, to string) ([]string, int) {
    // 查找起点和终点的索引
    var fromIdx, toIdx int
    for i, loc := range ns.locations {
        if loc.name == from {
            fromIdx = i
        }
        if loc.name == to {
            toIdx = i
        }
    }
    
    // 计算最短路径
    dist := ns.graph.DijkstraWithPQ(fromIdx)
    
    // 返回路径和距离
    return []string{from, to}, dist[toIdx]
}
```

### 网络路由

```go
type Router struct {
    id       int
    name     string
    capacity int
}

type Network struct {
    routers []Router
    graph   *Graph
}

func (n *Network) FindBestRoute(source, target int) []int {
    dist := n.graph.DijkstraWithPQ(source)
    
    // 构建路径
    path := make([]int, 0)
    current := target
    for current != source {
        path = append([]int{current}, path...)
        // 找到前驱节点（实际应用中需要记录前驱）
        current = source // 简化示例
    }
    path = append([]int{source}, path...)
    
    return path
}
```

## 性能分析

### 时间复杂度

1. 基本实现：
   - 查找最小距离顶点：O(V)
   - 更新距离：O(E)
   - 总体复杂度：O(V^2 + E) = O(V^2)

2. 优先队列优化：
   - 出队操作：O(log V)
   - 更新距离：O(E log V)
   - 总体复杂度：O(E log V)

### 空间复杂度

- 邻接表：O(V + E)
- 距离数组：O(V)
- 优先队列：O(V)
- 总体复杂度：O(V + E)

### 优化建议

1. 稀疏图使用优先队列实现
2. 稠密图使用基本实现
3. 考虑使用斐波那契堆优化（理论复杂度更优）
4. 对于特定应用可以使用双向搜索

## 总结

1. 算法特点：
   - 贪心策略
   - 适用于非负权重图
   - 求解单源最短路径

2. 实现考虑：
   - 根据图的特性选择实现方式
   - 注意数据结构的选择
   - 考虑实际应用场景的需求

3. 应用领域：
   - 导航系统
   - 网络路由
   - 社交网络
   - 物流配送