现在给你一个深圳地铁图。小明从市民中心上车，计算他到深圳所有地铁站所需时间(简化每个站到下一个站只花2分钟)。这就是迪杰斯特拉算法干的事。

历史：Dijkstra thought about the shortest path problem when working at the Mathematical Center in Amsterdam in 1956 as a programmer to demonstrate capabilities of a new computer called ARMAC. His objective was to choose both a problem as well as an answer (that would be produced by computer) that non-computing people could understand. He designed the shortest path algorithm and later implemented it for ARMAC for a slightly simplified transportation map of 64 cities in the Netherlands (64, so that 6 bits would be sufficient to encode the city number). A year later, he came across another problem from hardware engineers working on the institute's next computer: minimize the amount of wire needed to connect the pins on the back panel of the machine. As a solution, he re-discovered the algorithm known as  (known earlier to , and also rediscovered by Prim). Dijkstra published the algorithm in 1959, two years after Prim and 29 years after Jarník.。

大概意思就是D这个人呐在MC工作，他在检验当时一个叫ARMAC机的能力。他想设计一个问题和算法让普通人都能明白，于是拿起了荷兰64座城市地图。之后又做了一些事情，比如PRIM算法，以及利用这些算法解决了插接线的问题啥的。后来他在1959年就把这算法发表了。

代码：

#include 
     
       using namespace std; const int maxnum = 100; const int maxint = 999999; // 各数组都从下标1开始 int dist[maxnum]; // 表示当前点到源点的最短路径长度 int prev[maxnum]; // 记录当前点的前一个结点 int c[maxnum][maxnum]; // 记录图的两点间路径长度 int n, line; // 图的结点数和路径数 // n -- n nodes // v -- the source node // dist[] -- the distance from the ith node to the source node // prev[] -- the previous node of the ith node // c[][] -- every two nodes' distance void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum]) {     //步骤1------------初始化-------------bool s[maxnum]; // 判断是否已存入该点到S集合中    for(int i=1; i<=n; ++i)    {       dist[i] = c[v][i];       s[i] = 0; // 初始都未用过该点        if(dist[i] == maxint)           prev[i] = 0;        else            prev[i] = v;    }    dist[v] = 0;    s[v] = 1; // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中 // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 // 注意是从第二个节点开始，第一个为源点    //-----------步骤2--找到最小的并纳入-------------         //maxint 是无穷         //v是0点         //tmp是 找的最小点u的dis            for(i=2; i<=n; ++i)    {         int tmp = maxint;         int u = v;                    for(int j=1; j<=n; ++j)           if((!s[j]) && dist[j]
      
       =1; --i)         if(i != 1)             cout << que[i] << " -> ";         else             cout << que[i] << endl; } int main() {     freopen("input.txt", "r", stdin);     // 各数组都从下标1开始     // 输入结点数     cin >> n;     // 输入路径数     cin >> line;         int p, q, len; // 输入p, q两点及其路径长度     // 初始化c[][]为maxint         for(int i=1; i<=n; ++i)         for(int j=1; j<=n; ++j)             c[i][j] = maxint;                         for(i=1; i<=line; ++i)         {            cin >> p >> q >> len;            if(len < c[p][q]) // 有重边            {                c[p][q] = len; // p指向q                c[q][p] = len; // q指向p，这样表示无向图            }         }                 for(i=1; i<=n; ++i)             dist[i] = maxint;                 for(i=1; i<=n; ++i)         {             for(int j=1; j<=n; ++j)                 printf("%8d", c[i][j]);                  printf("\n");         }         Dijkstra(n, 1, dist, prev, c);                 for(int k=1;k
      
     

 

例子：

 

算法步骤如下：

 

　　1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值

    若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

　 若不存在<V0,Vi>，d(V0,Vi)为∝

    2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S

    3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的

         距离值比不加W的路径要短，则修改此距离值

 

     重复上述步骤2、3，直到S中包含所有顶点，即S=T为止

 

	初始化	S1纳入2(10最小)	S1纳入4(30最小)	S1纳入3(50最小)	S1纳入5(60最小)
2	10	10	10	10	10
3	无穷	10+50<无穷 60	30+20< 60  50	50	50
4	30	10+无穷>30  30	30	30	30
5	100	10+无穷>100 100	30+60<100  90	50+10<90  60	60
S1	{1}	{1,2}	{1,2,4}	{1,2,4,3}	{1,2,4,3,5}
S2	{2,3,4,5}	{3,4,5}	{3,5}	{5}	{}
dis		Dis2=10	Dis4=30	Dis3=50	Dis5=60
pre	Pre2=1 Pre4=1 Pre5=1	pre3=2	Pre3=4 Pre5=4	Pre5=3