本文共 1880 字，大约阅读时间需要 6 分钟。

最近开始看一些关于最短路径的算法，有广度优先遍历以及深度优先遍历等，除此之外，觉得最实用的还是求最小生成树还有求一些实际问题中两点之间的最短路径问题，在图中的边附上权值以后，就是不同于单纯遍历的场景了。在此，我看了下Dijkstra算法，它是求单源最短路径算法，同时记录了到任意一点最短路的路径，缺点的话感觉复杂度有点大，由于是采用邻接矩阵存储，所以为O(n^2)。

好了，现在主要说一下Dijkstra算法的主要思想，其针对每一步应该是贪心算法的体现，但就整体而言，又是动态最优化的体现，就不纠结这个了。其实，算法是将未获得最短路径的与已获得最短路径的分为两个集合，比如说起点选择1，总共有N个点，则从剩余N-1个点中选择与1点相邻且最小的权值边对应的顶点，并且将该点与点1归为同一类，关于归类可以用visited[N]数组来表示，初始均置为0，已确定的就置为1，在接下来的寻找点的过程中当然也要满足未访问（即visited[j]=0）并且也要是最小权值，这么说可能有点迷糊，不过只要记住一点就行了：每个点都会用dist[j]代表j点距离点1的最短距离，所以只要最短集合里加入了一个新的点，它所带来的改变就是会影响邻接与新加的点距离与点1的最短距离，即代码中的距离更新说明。那么接下来直接看代码吧。

#include 
   
    using namespace std;#define maxnum 100//最大顶点数#define maxint 9999//最大权值void Dijkstra(int n,int v,int *dist,int *prev,int c[maxnum][maxnum]){    bool s[maxnum];//s数组，即符合最短路径的集合    memset(s,0,sizeof(s));//初始化均未访问    for (int i=1;i<=n;i++)    {        dist[i] = c[v][i];        if (dist[i]==maxint)        {            prev[i] = 0;        }        else        {            prev[i] = v;        }    }    dist[v] = 0;    s[v] = 1;//设置起始点已访问，且起始到起始点距离为0    for (int i=2;i<=n;++i)//再寻找剩下的n-1个节点    {        int tmp = maxint;        int u = v;        for (int j=1;j<=n;++j)        {            if ((!s[j]) && dist[j]
    
     =1;--j)//打印路径    {        if (j!=1)        {            cout<
     
      <<"->";        }        else            cout<
      
       <
       
        >n>>edgenum)    {        for (int i=1;i<=n;i++)            for (int j=1;j<=n;j++)                c[i][j] = maxint;        int p,q,weight;        for (int i=1;i<=edgenum;i++)        {            cin>>p>>q>>weight;            if (weight < c[p][q])            {                 c[p][q] = c[q][p] = weight;            }        }        for (int i=1;i<=n;i++)        {            dist[i] = maxint;        }        for (int i=1;i<=n;++i)//打印权值矩阵        {            for (int j=1;j<=n;j++)            {                cout<
       
      
     
    
   

最终结果为