本文共 2064 字，大约阅读时间需要 6 分钟。

Dijkstra算法：

用途：求单源最短路径，有向图，无向图，边权为正，，正权图上的单源最短路，既从单个源点出发，到所有结点的最短路。

伪代码：

清除所有点的编号d[0]=0,其他d[i]=INF;循环n次{    在所有没标记的点中找出d最小的结点x；    标记x    对于从x结点出发的所有（x，y）    更新 d[y]=min(d[y],d[x]+w[x][y]);}

Dijkstra1(int x){    memset(vis,0,sizeof(vis));    for(int i=0; i<=n; i++) dis[i]=INF;    d[x]=0;    for(int i=0; i
   
    dis[pos]+w[pos][j])            {                dis[j]=dis[pos]+w[pos][j];                p[j]=pos;//可以用于记录路径            }        }    }}
   

稀疏图可以用vector表示，除此之外，还可以用邻接表表示。在这种表示法中，每一个结点i都有一个链表，里面保存着从i出发的所有边，对于无向图来说，每条边都会在邻接表中出现两次，

用数组实现邻接表，首先给每一条边编号，然后用fist保存结点u的第一条边，next表示下一条边，程序如下

Dijkstra2(){    int m,n;    int  first[MAXN];    int next[MAXN];    int u[MAXN],e[MAXN],v[MAXN];    memset(first,-1,sizeof(first));///进行初始化    int x,y,z;    for(int i=0; i

使用结构体储存

struct Edge{    int from,to,dist;    Edge(int u,int v,int d):from(u),to(v),dist(d){}};struct HeapNode{    int d,u;    bool operator<(const HeapNode &rhs)const    {        return d>rhs.d;    }};struct Dijkstra{    int n,m;    vector
   
     edges;    vector
    
      G[maxn];    bool done[maxn];    int p[maxn];    int d[maxn];    void Init(int n)    {        n=n;        for(int i=0;i<=n;i++)        {            done[i]=false;            G[i].clear();        }        edges.clear();    }    void ADDEdge(int from,int to,int dis)    {        edges.push_back(Edge(from,to,dis));        m=egdes.size();        G[from].push_back(m-1);    }    void dijkstra(int s)    {        priority_queue
     
       Q;        memset(done,0,sizeof(done));        for(int i=0;i<=n;i++)            d[i]=INF;        d[s]=0;        HeapNode h(0,s);        Q.push(h);        while(!Q.empty())        {            HeapNode hh=Q.top();            int u=hh.u;            Q.pop();            if(done[u]) continue;            done[u]=true;            for(int i=0;i
      
       d[u]+e.dist)                {                    p[e.to]=G[u][i];                    d[e.to]=d[u]+e.dis;                    Q.push((HeapNode){d[e.to],e.to});                }            }        }    }};
      
     
    
   

转载地址：http://dygsi.baihongyu.com/