有向图中Dijstra最短路径算法的邻接表实现

网上和书本上很多Dijstra算法的邻接矩的实现，但是对于稀疏图，邻接矩实现方法产生了很多不必要的开销。故此，采用邻接表实现较为合适。

首先将图转换为邻接表表示，本人并没有做传统意义的邻接表，而是用的点索引其出度边。

第一步：图的处理：

建立4个vector数据结构去存储4个顶点的出度，建立边的数据结构存储边的信息.例：

struct edge
{
   int id;
   int from;
   int to;
   int weight;
};
vector<int> node[] = [,,];
           

第二步：初始化：

node	konwn	dis(无穷大的数)	pre
false	100000	-1
1	false	100000	-1
2	false	100000	-1
3	false	100000	-1

node为点的编号

known为到该点的最短路径是否已知

dis为起点到该点的最短路径

pre为引起该点dis变化的最后一个node的编号

代码示例：

struct Station
{
    int id;
    bool known;
    int dir;
    int pre;
    friend bool operator<(Station a,Station b)
    {
        return a.dir > b.dir;
    }
};
Station node_station[node_num];
for(int i=;i<=node_num;i++)
  {
    node_station[i].id = i;
    node_station[i].known = false;
    node_station[i].dir = max_num;//本例设为
    node_station[i].pre = -;
  }
           

第三步：算法实现

vector<int>  Digstra_zheng_weigh(int start_p,int end_p,vector<int>* node_temp)
{
    for(int i=;i<=max_node_num;i++)
    {
        node_station[i].id = i;
        node_station[i].known = false;
        node_station[i].dir = max_num;
        node_station[i].pre = -;
    }
    priority_queue<Station> q;//点的状态的优先队列
    node_station[start_p].dir = ;//起点到起点的距离为
    node_station[start_p].known =true;//起点设为已知
    q.push(node_station[start_p]);//起点压进队列
    while(!q.empty())
    {
        Station this_p = q.top();//当前计算起始点
        q.pop();//该点已经使用，出队列
        int u = this_p.id;//该点的id
        if(node_station[u].known) //如果该点已经已知，下一个
              continue;
        node_station[u].known = true;//该点设为已知
        vector<int> edge_temp = node_temp[u];//当前节点的出度<边>
        for(int j=0;j<edge_temp.size();j++)
        {
            int id_n = edge_point[edge_temp[j]].to;
            if(!node_station[id_n].known && node_station[id_n].dir > node_station[u].dir + edge_point[edge_temp[j]].weight )
            {

                node_station[id_n].dir = node_station[u].dir + edge_point[edge_temp[j]].weight;
                node_station[id_n].pre = u;
                q.push(node_station[id_n]);
            }
        }
    }
    vector<int> out;
    out.clear();
    if(node_station[end_p].known)
    {
        int n = end_p;
        while(node_station[n].pre != -1)
        {
            //out.insert(out.begin(),n);
            n = node_station[n].pre;
            out.insert(out.begin(),n);
        }
        if(node_station[end_p].known)
            this_route_weight += node_station[end_p].dir;
        //out.insert(out.begin(),n);
    }
    return out;
}

           

简述算法流程：

Dijstra(int start,vector<int> node)
{
   、init_node_station();//初始化所有点的状态
   、start点的dis设为，known设为true；将所有start点能到的点的dis设为对应边的权重，pre设为start
 while(){  
 取所有dis中最短的点P设为新的起点，如果该点的known为true，退出循环；否则，将该点known设为true，
   判断P点能到达的点M[i]，
       if(!station[M[i].known)
          if(station[M[i].dis > station[P].dis +  该边的权重)
          {
             station[M[i]].dis = station[P].dis +  该边的权重
             station[M[i]].pre = P
          }
    }
}
//这时，若该点的known为true，则该点的dis为起点到该点的最短距离