一、Dijkstra算法的基本思想
    
    首先引进一个辅助向量D，其每个分量D[]表示当前阶段从起点start到顶点i所计算出的最短路径。初始化之为：D[start]为0，其余D[]为“无穷大”。
    在每个阶段，该算法选择所有顶点中D[]最小的未知顶点，将其标记为已知，然后对其所有的邻接顶点的D[]进行更新(若新的D[]更小的话)，然后进入下一阶段，直至所有顶点均已知。
    
    为什么这样做是对的？
    令某阶段下所有的已知顶点构成集合S，则当前阶段选择的D[]最小的v的最短路径上的点必然存在于S中。
    用反证法来证明之之：
    算法是按照路径长度的递增来构成S，假设v的最短路径L上有一点w不在S内，即w是一个未知顶点。
    1.因为w处于L上，所以start到w路径要比L短。得出 D[w] < D[v]
    2.v是当前阶段选择的D[]最小的未知点，故 D[w] > D[v]
    结论1和结论2相悖。所以刚才的假设错误。此反证法证明了Dijkstra算法的正确性。

二、伪代码

Dijsktra( D, G, start )
{
        Init D[];
        while ( select an unknown v which has a smallest D[v] )
        {
                for each w adjacent of v
                {
                        if ( D[w] will be smaller )
                        {
                                update D[w];
                        }
                }
        }
}

三、ANSI C 代码

typedef int Bool;
#define TRUE  ( 1 )
#define FALSE ( 0 )

#define NULL             ( 0 )
#define NOT_A_VERTEX     ( 0 )
#define INFINITY         ( 0xFFFFFFF )
#define MAX_NUM_VERTICES ( 100 )

/* use adjacent list to represent a graph */
/* Vertices are numbered from 1 */
/* 0 express an inexistent vertex */
typedef int Weight;
typedef unsigned int Vex;
typedef struct edge
{
        Vex vex;
        Weight weight;
        struct edge* next;
}* Edge;
typedef struct vertex
{
        Edge first;
}* Vertex;
typedef struct graph
{
        Vertex vertices[MAX_NUM_VERTICES];
        int num_vertices;
}* Graph;

/* select an unknown vertex which has a smallest D[] */
/* if there are not unknows vertices, it will return NOT_A_VERTEX */
Vex Select( Weight D[], Bool known[], int n );

/* Dijkstra's Algorithm */
/* D[i] will be the weight of the Shorest-Path from start to i */
/* P[i][] will contain all the vertices on the Shorest-Path from start to i */
/* the Shorteset-Path in P[][] will be ended by 0 */
void Dijkstra(  Weight D[], Vex P[][MAX_NUM_VERTICES], Graph G, Vex start )
{
        Bool known[MAX_NUM_VERTICES] = { FALSE };
        Vex* tailP[MAX_NUM_VERTICES] = { NULL  }; /* use to update P[][] */

        Vex v;
        int i;
        Edge edge = NULL;

        /* Initialize D[], P[] and tailP[] */
        for ( v = 1; v <= G->num_vertices; ++v )
        {
                D[v] = INFINITY;
                for ( i = 0; i < MAX_NUM_VERTICES; ++i )
                {
                        P[v][i] = 0;
                }
                tailP[v] = P[v];
        }
        D[start] = 0;

        /* start Dijkstra */
        while ( ( v = Select( D, known, G->num_vertices ) ) != NOT_A_VERTEX )
        {
                *tailP[v] = v;
                known[v] = TRUE;

                /* update each vex adjacent to v if it need to be updated */
                for ( edge = G->vertices[v]->first; edge != NULL; edge = edge->next )
                {
                        if ( ( D[v] + edge->weight ) < D[edge->vex] )
                        {
                                D[edge->vex] = ( D[v] + edge->weight );
                                *tailP[edge->vex]++ = v; /* update P[][] */ 
                        }
                }
        }
        return;
}

/* select an unknown vertex which has a smallest D[] */
/* if there are not unknows vertices, it will return NOT_A_VERTEX */
Vex Select( Weight D[], Bool known[], int n )
{
        Vex v, w;
        Weight min = INFINITY;
        
        v = NOT_A_VERTEX;
        for ( w = 1; w <= n; ++w )
        {
                if ( !known[w] && ( D[w] < min ) )
                {
                        v = w;
                        min = D[w];
                }
        }
        return v;
}

四、该算法时间复杂的分析

    外循环每个顶点要选取并标记一次 O(|V|)，求D[]最小的未知顶点要遍历所有点 O(|V|)，每个点对周围点更新等于遍历所有的弧 O(|E|)
    所以该算法总时间复杂度 O(|V|^2+|E|)