1、对于每条边仅松弛一次

2、复杂度低于Bellmall-Ford

3、边的权重为非负值

4、时间复杂度O（V*lgV）

INITIALIZE-SINGLE-SOURCE(G,s)

for ecah vertex v属于G.V

     v.d=MAXINT

     v.prev=NULL

s.d=0

伪码：

DIJKSTRA(G,w,s)

INITIALIZE-SINGLE-SOURCE(G,s)

S=NULL

Q=G.V

while Q!=NULL

     u=EXTRACT-MIN(Q)

     S=S U {u}

     for each vertex v属于G.Adj[u]

          RELAX(u,v,w)

c++实现：

namespace A{
       int prev[100];//各个节点的前驱节点
       int dist[100];//各个节点到源节点的最短距离
       int c[100][100];//用临接矩阵表示图
       bool s[100];//表示节点是否已经加入S集合
       int nodenum;//节点个数
       int line;//边的条数
       int startnode;//源节点
       int src, dst, weight;
       const int MAXINT = 9999;

       void init()
       {
              cout << "输入节点个数:"; cin >> nodenum;
              cout << "输入边的条数："; cin >> line;
              cout << "输入源节点编号:"; cin >> startnode;
              for (int i = 1; i <= nodenum; ++i){
                     for (int j = 1; j <= nodenum; ++j)
                           c[i][j] = MAXINT;
              }
              cout << "输入" << line << "行src dst wight:";
              for (int i = 1; i <= line; ++i){
                     cin >> src >> dst >> weight;
                     c[src][dst] = weight;
                     //c[dst][src]=weight;//无向图
              }
              for (int i = 1; i <= nodenum; ++i){
                     dist[i] = c[startnode][i];
                     if (dist[i] == MAXINT)
                           prev[i] = -1;
                     else
                           prev[i] = startnode;
              }
              dist[startnode] = 0;
              for (int i = 1; i <= nodenum; ++i){
                     s[i] = false;
              }
              s[startnode] = true;
       }
       void Dijkstra()
       {
              init();
              int scount = 1;
              while (scount < nodenum){
                     int tmp = MAXINT;
                     int u;
                     for (int i = 1; i <= nodenum; ++i){
                           if (s[i] == false && dist[i] < tmp) {
                                  tmp = dist[i];
                                  u = i;
                           }
                     }
                     s[u] = true;
                     for (int i = 1; i <= nodenum; ++i){
                           if (s[i] == false && c[u][i] < MAXINT&&c[u][i] + tmp < dist[i]){
                                  dist[i] = c[u][i] + tmp;
                                  prev[i] = u;
                           }
                     }
                     ++scount;
              }
       }
};
int main()
{
       A::Dijkstra();
       for (int i = 1; i <= A::nodenum; ++i)
              cout << A::dist[i] << " ";
       cout << endl;
       system("pause");
       return 0;
}

测试用例：

5

7

1

1 2 10

1 4 30

1 5 100

2 3 50

3 5 10

4 3 20

4 5 60

《完》

本文出自 “零蛋蛋” 博客，谢绝转载！

Dijkstra