算法分析与实践-作业2-Dijkstra算法求最短距离

1. 问题

对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

2. 解析

Dijkstra算法通过从起始节点往相邻节点不断进行扫描，更新dist数组、path数组和set数组。然后遍历set集合中设0的顶点，假如扫描点为b点，接下来遍历顶点c、d、e、f、g和h。首先是c点，从a=>b=>c没有直接相邻线段，所以a=>b=>c距离设置为无穷大，不对dist和path进行更新；然后d点……

3. 设计

    for(i = 0; i < N; i++){
        min_dis = INF;
        for(j = 0; j < N; j++){
            if(used[j] == 0 && distance[j] < min_dis){
                min_node = j;
                min_dis = distance[j];
                pass_flag++; // 标记是否存在通路
            }
        }
        if(pass_flag != 0){
            used[min_node] = 1;
            for(j = 0; j < N; j++){
                if(used[j] == 0){
                    if(adj_arr[min_node][j] < INF && distance[min_node] + adj_arr[min_node][j] < distance[j]){
                        distance[j] = distance[min_node] + adj_arr[min_node][j];
                        path[j] = min_node;
                    }
                }
            }
        }else{
            printf("There is no path!\n");
            return;
        }
}

4. 分析

在shortest_path()函数中存在两个长度为N的for循环，故其时间复杂度为O(n^2)。

5. 源码

https://github.com/kekekeQWQ/2-2