Dijkstra 模板

void Dijkstra(int v0)
{
  　　bool S[MAXNUM];                                  // 判断是否已存入该点到S集合中
      int n=MAXNUM;
  　　for(int i=1; i<=n; ++i)
 　　 {
      　　dist[i] = A[v0][i];
      　　S[i] = false;                                // 初始都未用过该点
      　　if(dist[i] == MAXINT)    
            　　prev[i] = -1;
 　　     else 
            　　prev[i] = v0;
   　　}
   　 dist[v0] = 0;
   　 S[v0] = true; 　　
 　　 for(int i=2; i<=n; i++)
 　　 {
       　　int mindist = MAXINT;
       　　int u = v0; 　　                            // 找出当前未使用的点j的dist[j]最小值
      　　 for(int j=1; j<=n; ++j)
      　　    if((!S[j]) && dist[j]<mindist)
      　　    {
         　　       u = j;                             // u保存当前邻接点中距离最小的点的号码 
         　 　      mindist = dist[j];
       　　   }
       　　S[u] = true; 
       　　for(int j=1; j<=n; j++)
       　　    if((!S[j]) && A[u][j]<MAXINT)
       　　    {
           　    　if(dist[u] + A[u][j] < dist[j])     //在通过新加入的u点路径找到离v0点更短的路径  
           　    　{
                   　　dist[j] = dist[u] + A[u][j];    //更新dist 
                   　　prev[j] = u;                    //记录前驱顶点 
            　　    }
        　    　}
   　　}
}

int dijkstra(int n)
{
    //初始化v[0]到v[i]的距离
    for(int i=1;i<=n;i++)
        dis[i] = w[0][i];                                       
    vis[0]=1;//标记v[0]点
    for(int i = 1; i <= n; i++)
    {
        //查找最近点
        int min = INF,k = 0;
        for(int j = 0; j <= n; j++)
            if(!vis[w] && dis[j] < min)
                min = dis[w],k = j;
        vis[k] = 1;//标记查找到的最近点
        //判断是直接v[0]连接v[j]短，还是经过v[k]连接v[j]更短
        for(int j = 1; j <= n; j++)
            if(!vis[j] && min+w[k][j] < dis[j])
                d[j] = min+w[k][j];
    }
    return dis[j];
}

堆优化

#include<iostream>
#include<vector>
#include<queue>

#define MAXN 10005
#define INF  0x7fffffff

using namespace std;
struct edge{
    int to;
    int wt;
    edge(int to_,int wt_):to(to_),wt(wt_){};
    /*bool operator< (edge& b){
        return val<b.val;
    }
    edge(){};
    edge(int from_,int to_,int val_):from(from_),to(to_),val(val_){};*/
};
struct node{
    int to;
    int val;
    bool operator<(node& b){
        return val<b.val;
    }
    node(int to_,int val_):to(to_),val(val_){};
    node(){};
};
vector<edge> adj[MAXN];
typedef vector<edge>::iterator it;
priority_queue<node, vector<node>,less<node> > heap;
int vis[MAXN]={0};
int dis[MAXN]={0};
int prev[MAXN]={0};
void add(int from,int to,int wt){
    adj[from].push_back(edge(to,wt));
}
void dijkstra(int from,int n){

    for(int i=1;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }
    dis[from]=0;
    heap.push(node(from,0));

    for(int i=1;i<=n;i++){
        node now;
        while(vis[(now=heap.top()).to])
            heap.pop();
        heap.pop();
        vis[now.to]=1;
        for(it i=adj[now.to].begin();i!=adj[now.to].end();++i){
            if(dis[now.to]+i->wt<dis[i->to]){
                dis[i->to]=dis[now.to]+i->wt;
                heap.push(node(i->to,dis[i->to]));
            }
        }
    }
}
int main(){
    int from,n;
    cin>>n;
    cin>>from;
    int m;
    int from,to,wt;
    for(int i=1;i<=m;i++){
        cin>>from>>to>>wt;
        add(from,to,wt);
    }
    dijkstra(from,n);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    cout<<endl;
    return 0;
}