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; 　　                            // 找出當(dāng)前未使用的點j的dist[j]最小值
      　　 for(int j=1; j<=n; ++j)
      　　    if((!S[j]) && dist[j]<mindist)
      　　    {
         　　       u = j;                             // u保存當(dāng)前鄰接點中距離最小的點的號碼 
         　 　      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;                    //記錄前驅(qū)頂點 
            　　    }
        　    　}
   　　}
}

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]短贰您，還是經(jīng)過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];
}

堆優(yōu)化

#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;
}