最短路径(Dijkstra算法)

人有一个特点，一个字就是懒，纵观世界上的交通发展史，从步行到马车，再到自行车，汽车，再到飞机、轮船火箭，归咎到底就是人想要更快更便捷的到达自己想去的地方，除了交通工具的升级，当然人们也在探索“最短路径”，最短路径问题是组合优化领域的经典问题之一，他广泛用于计算机科学、交通工程、通信工程等领域。

在进行了离散数学的学习之后我又去查阅了迪杰斯特拉（Dijkstra）算法的资料，Dijkstra算法是由荷兰科学家迪克斯特拉在1959年提出，从一个顶点到其余各顶点的最短路径算法，主要特点是以起始点为中心向外层层扩展，直到扩展到终点。

Dijkstra算法具体的原理我将从一个实际问题出发来解释。

假设我放假要出去玩，我发誓要逛遍所有日照市的海洋公园、海滨公园、香河公园、兴海公园，但是我必须先去海洋公园或者海滨公园，因为他俩太抢手，然后再从海洋公园去香河公园，或兴海公园，但是由于今天修路，海洋公园到兴海公园的路没了，通过这些需求，我在百度地图画了画路线，是这样子的：

地图

通过简化得到酱紫的图像：

线图

对图像进行标准化并剔除海滨公园到香河公园较长的路线，经过美化得到如下图：

简化美化图

接下来问题就转换成了从“1”分别到“2”，“3”，“4”，“5”的最短路径，首先我们先用数据结构存储图的信息：

ｅ	１	２	３	４	５
１	０	３．９	６．５	∞	∞
２	∞	０	３．５	１２．３	∞
３	∞	∞	０	１０．６	１２
４	∞	∞	∞	０	３．７
５	∞	∞	∞	∞	０

我们还需要一个一维数组"arr"来存储“1”号顶点到其余各个顶点的初始路程，即：

	1	2	3	4	5
arr	0	3.9	6.5	∞	∞

通过上述表格我们发现由“1”到“2”和“3”分别是3.9和6.5最近的是点“2”,因此点“2”确定：

	1	2	3	4	5
arr	0	3.9	∞	∞	∞

接下来从“2”发现到“3”最近，因此“3”点确定：

	1	2	3	4	5
arr	0	3.9	7.4	16.2	∞

即：

	1	2	3	4	5
arr	0	3.9	7.4	∞	∞

接下来从"3"到"4"和"5"发现"4"较近即"4"确定：

	1	2	3	4	5
arr	0	3.9	7.4	18	19.4

即：

	1	2	3	4	5
arr	0	3.9	7.4	18	∞

最后从“4”到“5”：

	1	2	3	4	5
arr	0	3.9	7.4	18	21.7

即Dijkstra算法算是贪心算法实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

来自百度百科代码实现：

#include

#include

#define max1 10000000  //原词条这里的值太大，导致溢出，后面比较大小时会出错

int a[1000][1000];

int d[1000];//d表示源节点到该节点的最小距离

int p[1000];//p标记访问过的节点

int i, j, k;

int m;//m代表边数

int n;//n代表点数

int main()

{

    scanf("%d%d",&n,&m);

    int    min1;

    int    x,y,z;

    for(i=1;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        a[x][y]=z;

        a[y][x]=z;

    }

    for( i=1; i<=n; i++)

        d[i]=max1;

    d[1]=0;

    for(i=1;i<=n;i++)

    {

        min1 = max1;

        //下面这个for循环的功能类似冒泡排序，目的是找到未访问节点中d[j]值最小的那个节点，

        //作为下一个访问节点，用k标记

        for(j=1;j<=n;j++)

            if(!p[j]&&d[j]d[k]+a[k][j])

                d[j]=d[k]+a[k][j];

    }

    //最终输出从源节点到其他每个节点的最小距离

    for(i=1;i",d[i]);

    printf("%d\n",d[n]); 

    return 0;

}