数据结构(十五)dijkstra单源最短路径

喜欢ヅ旅行 2022-05-31 13:38 170阅读 0赞

### **1 算法原理** ###

假设图中有顶点V=\{A，B，C，D，E，F\}，我们要求取A到其他顶点的最短距离。假设我们要求取定点A到其它顶点的最短路径，先把顶点A到源的距离设置为0，其他的距离设置为无穷大。准备两个集合S\_frozeen=\{\}，S\_inactive=\{A，B，C，D，E，F\}，S\_frozeen我们称之为源，单源最短路径的的原理就是：每次提取S\_inactive中离源S\_frozeen最近的顶点，添加到源S\_frozeen中，n个顶点，需要添加n次，直到S\_inactive为空为止。

A、拿出S\_inactive中离源S\_frozeen最近的点A，得到S\_frozeen=\{A\}，更新S\_inactive=\{B，C，D，E，F\}中的顶点到源S\_frozeen=\{A\}的距离；

B、继续查找里S\_inactive中离S\_frozeen最近的点，然后加入S\_frozeen中，并更新S\_inactive顶点到源的距离，如果是稀疏图可以只更新邻接顶点。

因此dijkstra的主要思想在于：把S\_frozeen中的顶点，当做一整个源，往源中不断添加非源中的顶点，主要是添加的优先顺序，根据到源的最短距离。

### **2 代码实现** ###

例子：[http://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html][http_wiki.jikexueyuan.com_project_easy-learn-algorithm_dijkstra.html]。

![20180226161422166][]

![20180226161431552][]

假设源点为1，其它点到源点的最短距离：0、1、8、4、13、17。

#include <vector>
    #include <limits>
    
    using namespace std;
    class dijkstra{
    public:
        dijkstra(){};
        ~dijkstra(){};
        class node{
        public:
    
            node(){
                S_flag= false;
                distance_to_src=1e5;
                pre_node=-1;
            };
            ~node(){};
            bool S_flag;
            int pre_node;
            int distance_to_src;
        };
        //求0号定点到1,2,3,4,5定点的最短路径
        std::vector<std::vector<int>> example_graph(){
    
            float max_number=1e5;
            int node_number=6;
            std::vector<std::vector<int>>graph(node_number);
            for (int i = 0; i <graph.size() ; ++i) {
                graph[i].resize(node_number,max_number);
                graph[i][i]=0;
            }
            graph[0][1]=1;
            graph[0][2]=12;
    
            graph[1][2]=9;
            graph[1][3]=3;
    
            graph[2][4]=5;
    
    
            graph[3][2]=4;
            graph[3][4]=13;
            graph[3][5]=15;
    
            graph[4][5]=4;
    
            return graph;
        }
    
    
        void main(){
            std::vector<std::vector<int>>graph=example_graph();
            int n=graph.size();
            std::vector<node>nodes(n);
            nodes[0].distance_to_src=0;
    
            for (int step = 0; step <n ; ++step) {//S_inactive中有n个顶点，要每次提取一个点离S_frozeen最近的点扔到源中，直到S_inactive为空，所以需要遍历n次
    
                //第一步：寻找S_inactive中离源最近的点id号min_index
                int min_dist=1e5;
                int min_index=-1;
                for (int j = 0; j <n ; ++j) {
                    if(!nodes[j].S_flag)//S_inactive中的点
                    {
                        if(nodes[j].distance_to_src<min_dist)
                        {
                            min_dist=nodes[j].distance_to_src;
                            min_index=j;
                        }
                    }
                }
                if(min_index<0)break;
    
    
                //第二步：添加min_index到S_frozeen中，并更新S_inactive到源S_frozeen的距离（只需要更新min_index的邻居顶点就可以了）
                nodes[min_index].S_flag=true;//添加到S_frozeen
                for (int j = 0; j < n; ++j) {//更新S_inactive到源S_frozeen的距离
                    if (!nodes[j].S_flag)
                    {
                        int new_idst=graph[min_index][j]+nodes[min_index].distance_to_src;
                        if(nodes[j].distance_to_src>new_idst)
                        {
                            nodes[j].distance_to_src=new_idst;
                            nodes[j].pre_node=min_index;
                        }
    
                    }
    
                }
    
    
            }
            
            for (int i = 0; i <n ; ++i) {
                std::cout<<nodes[i].distance_to_src<<std::endl;
            }
    
        }
        
    };

[http_wiki.jikexueyuan.com_project_easy-learn-algorithm_dijkstra.html]: http://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html
[20180226161422166]: /images/20220531/bf5c8aeba197402db696885606873e73.png
[20180226161431552]: /images/20220531/04fd85b5f3a74039ac7702e4885d0c8b.png