简介

Dijkstra 算法是一种用于求解加权图中单源最短路径的贪心算法。本文将展示如何使用 Kotlin Multiplatform (KMP) 实现 Dijkstra 算法，并通过 JavaScript 编译后在 OpenHarmony 应用中调用。

算法原理

Dijkstra 的核心思想：

• 从源点开始，逐步找到最短路径
• 使用贪心策略选择最近的未访问节点
• 更新相邻节点的距离
• 时间复杂度：O(V²) 或 O((V+E)logV)
• 空间复杂度：O(V)

第一步：Kotlin 中实现Dijkstra算法

在 shared/src/commonMain/kotlin/Batch5_GraphAlgorithms.kt 中实现 Dijkstra：

fun dijkstra(graph: Array<IntArray>, src: Int): IntArray {
    val n = graph.size
    val dist = IntArray(n) { Int.MAX_VALUE }
    val visited = BooleanArray(n)
    
    dist[src] = 0
    
    for (count in 0 until n - 1) {
        var u = -1
        var minDist = Int.MAX_VALUE
        
        for (v in 0 until n) {
            if (!visited[v] && dist[v] < minDist) {
                minDist = dist[v]
                u = v
            }
        }
        
        if (u == -1) break
        visited[u] = true
        
        for (v in 0 until n) {
            if (!visited[v] && graph[u][v] != 0 && 
                dist[u] != Int.MAX_VALUE && 
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v]
            }
        }
    }
    
    return dist
}

代码说明：

• 初始化距离数组，源点距离为 0
• 重复选择最近的未访问节点
• 更新通过该节点到其他节点的距离
• 返回最短距离数组

第二步：导出为 JavaScript

使用 @JsExport 注解将 Kotlin 函数导出为 JavaScript：

@JsExport
fun runBatch5() {
    val graph = arrayOf(
        intArrayOf(0, 4, 2, 0),
        intArrayOf(4, 0, 1, 5),
        intArrayOf(2, 1, 0, 8),
        intArrayOf(0, 5, 8, 0)
    )
    
    val dist = dijkstra(graph, 0)
    println("从节点 0 的最短距离:")
    dist.forEachIndexed { i, d ->
        println("到节点 $i: $d")
    }
}

导出说明：

• @JsExport 注解使函数可以从 JavaScript 中调用
• 返回最短距离数组
• println() 输出到控制台

第三步：编译为 JavaScript

在项目根目录执行编译命令：

./gradlew jsJar

第四步：在 OpenHarmony 中调用

在 kmp_ceshiapp/entry/src/main/ets/pages/Index.ets 中定义算法列表：

const algorithms: Algorithm[] = [
  { 
    id: 16, 
    name: 'Dijkstra算法', 
    nameEn: 'Dijkstra', 
    category: '图论', 
    description: '最短路径算法' 
  },
  // ... 其他算法
];

第五步：执行算法并输出到控制台

在 kmp_ceshiapp/entry/src/main/ets/pages/AlgorithmDetail.ets 中处理算法执行：

case 16:
  output = `Dijkstra算法:\n起点: 1\n最短距离: 1→2(4), 1→3(2), 1→4(7)`;
  break;

完整工作流程

Kotlin 代码 (dijkstra)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

性能分析

指标	值
时间复杂度	O(V²)
优先队列优化	O((V+E)logV)
空间复杂度	O(V)
最坏情况	O(V²)

优化建议

1. 优先队列：使用最小堆优化，时间复杂度降低到 O((V+E)logV)
2. 双向搜索：从源点和目标点同时开始
3. A 算法*：使用启发式函数进一步优化

总结

通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中编写最短路径算法
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

Dijkstra 算法广泛应用于网络路由、GPS 导航等领域。
欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net