最短路问题——Djikstra

· · 算法·理论

最短路问题—— Dijkstra

虽然并不是完全掌握

例题：

  1. P3371 【模板】单源最短路径（弱化版）
  2. P4779 【模板】单源最短路径（标准版）
  3. Dijkstra?
  4. P5905 【模板】全源最短路（Johnson）
  5. P1144 最短路计数

Dijkstra 的条件：

  1. 用于求最短路问题
  2. 确定起点

思想

运用贪心的思想，在当前起点的出边中找到 未被遍历 过的边权最小的点，将其标记并更新最短路径，直到遍历到终点。

实现：

  1. 邻接矩阵
    时间复杂度 O(n^2)。

    //map是邻接矩阵数组，map[i][i] = 0,若i,j之间没有边则map[i][j] = INF 
void Djikstra(int x){//x是起点 
memset(d,INF,siziof(d));//求最短，初始化为较大数
d[x] = 0;//到他本身
for(int i = 1;i <= n;i++){
    int j = 0;//当前最小 
    for(int k = 1;k <= n;k++){//找最小的未被访问的d[j] 
        if(!vis[k] && d[k] <= d[j]){
            j=k;
        }
    }
    vis[j] = 1;
    for(int k = 1;k <= n;k++){//更新d[j] 
        d[k] = min(d[k],d[j] + map[j][k]);
    }
} 
}

  2. 邻接表

时间复杂度 O(n^2)。

//head是表头,ver是当前边的指向的点,nxt是下一条边,data是权值 
void Djikstra(int x){//x是起点 
    memset(d,INF,siziof(d));//求最短，初始化为较大数
    d[x] = 0;//到他本身
    for(int i = 1;i <= n;i++){
        int j = 0;//当前最小 
        for(int k = 1;k <= n;k++){//找最小的未被访问的d[j] 
            if(!vis[k] && d[k] <= d[j]){
                j=k;
            }
        }
        vis[j] = 1;
        for(int k = head[j];k != -1;k = nxt[k]){//更新d[j] 
            d[ver[k]] = min(d[ver[k],d[j]]+data[k]);
        }
    } 
}

堆（优先队列）优化

优化条件

  1. 边权非负
  2. 边数远小于n^2，即cnt(edge) \le 2\cdot10^5

    vector做法

    时间复杂度 O(m\cdot log_2m)

    
struct node{
int d;//d是当前的最短路径 
int u;//u是起点 
bool operator < (const node & rhs) const {
    return d > rhs.d;
}//重载运算符
};

vector <int> e[N];//e[i][]表示第i个点所连的所有边 vector <int> w[N];//w[i][]表示e[i][]所连边的权值

void Dijkstra(){

priority_queue <node> q;
F(2,i,n) d[i]=INF;
node tn;
tn.d=0,tn.u=1;
q.push(tn);
int u;
    //初始化 

while(!q.empty()){
    node t=q.top();
    q.pop();
    u=t.u;
    if(vis[u]) continue;//要求未被标记
    vis[u]=1;
    for(int i = 0;i < e[u].size();i++){//vector默认从0开始，遍历从u到达的边       
        int v = e[u][i];//v是终点
        if(d[v] > d[u] + w[u][i]){//这条路径的长度小于当前最短路径 
            d[v] = d[u] + w[u][i];//更新最短路径
            pre[v]=u;//记忆路径
            tn.d=d[v],tn.u=v;
            q.push(tn);//作为新起点入堆
        }
    } 
}

}



~~萌新第一次写博客~~