有向圖中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為起點到該點的最短距離