Dijkstra算法

Dijkstra算法

Dijkstra老爷子也是在计算机领域的名人了，在程序设计，编译器，操作系统，图论等方面都经常出现。他的一句最出名的名言就是：“有效的程序员不应该浪费时间用于程序调试，它们应该一开始就不要把故障已经纳入”，Dijkstra算法就是以他命名的常用的最短路径算法

Dijkstra算法的过程是:

第一步，先找到从源点到各个顶点的直达的路径，源点就是起点，简而言之你想求得从A0顶点到A9顶点的最短路径，那么A0就是源点，源点直达的路径就是与其直接相连的顶点的边，下图中A与B A与C就是直接相连的，而A和D不能直接到达而需要通过B和C所以不是直接相连的

第二步，在这些路径中找出一条长度最短的路径

第三步，然后对其余路径进行调整，若图中存在弧(u,vk) ，且(v0,u) + (u,vk) < (v0,vk)，就以路径(v0,uvk)代替(v0,vk)。在调整后的各条路径中再找长度最短的路径，依次类推

Dijkstra算法的思想就是按照路径的长度递增的次序产生最短的路径

1、首先是把顶点集V分为两组

S：已经求出最短路径的顶点的集合

T = V - S :没有找到最短路径的顶点集合

2、把T中顶点按最短路径递增的次序加入到S中

同时保证从源点到S中各顶点的最短路径的长度都不大于从源点到到T中任何顶点的最短路径长度，每一个顶点都要对应一个距离值，S中顶点是从源点到此顶点最短路径的长度，T中顶点是从源点到此顶点的只包括S中顶点作中间顶点的最短路径。

当然上面的解释可能难以理解，下面我会用一个例子说明

T顶点对应的距离用辅助数组D存放,开始时，S中只有源点，T中有除源点外的其他顶点，如果v0到vi是直接相连的，D[i]为权值，如果不是则为无穷大，从T中选取一个距离值最小的顶点vj，加入S。对T中顶点的距离值进行修改，一直重复上述过程，直到S = V为止

代码实现，参考了网上

#include<iostream>
using namespace std;

const int INF=99999999;  //无穷大数
int road[1000][1000]; //记录距离矩阵
int dist[1000]; //记录最短路径数组
bool visited[1005]; //记录是否已经搜过

//dijkstra最短路径算法，参数为顶点数目n、起始点start
void dijkstra(int n,int start)
{
    dist[start]=0;
    //依此遍历n个点，分别记录各点的最短路径
    for(int i=0;i<n;i++)
    {
        int s=-1;//下标
        int min=INF;//初始值
        //找到没有搜过且距离最小的点
        for(int j=0;j<n;j++)
        {
            if(visited[j]==false && dist[j]<min)
            {
                s=j;
                min=dist[j];
            }
        }
        if(s==-1) break;
        else 
        {
            visited[s]=true;
        }
        for(int v=0;v<n;v++)
        {
            //找到最短路径的话就更新
            if(visited[v]==false && dist[s]+road[s][v]<dist[v] && road[s][v]!=INF)
            {
                dist[v]=dist[s]+road[s][v];
            }
        }
    }
    //分别输出起始点到每个点的最短路径
    for(int i=0;i<n;i++)
    {
        cout<<dist[i]<<" ";
    }
}

int main()
{
    //输入n个城市、m条路径，以及开始搜索点
    int n,m,start;
    cin>>n>>m>>start;
    //初始化，都定义为无穷大
    fill(road[0],road[0]+1000*1000,INF);
    fill(dist,dist+1000,INF);
    //输入起点（a）、终点（b）、距离（c），并存入距离矩阵中
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        road[a][b]=c;
        road[b][a]=c;
    }
    //调用函数
    dijkstra(n,start);
    system("pause");
    return 0;

}

/*
测试用例
5 6 0 
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
*/