基础算法之Dijkstra最短路径

核心思想：以起始原点为中心，想外层扩展，知道扩展到重点为止。

设到A点的最短路径上，A点前驱节点为B，则该路径包含到达节点B的最短路径。

S集合代表已经探索过的节点，U集合表示未探索过的节点。

时间复杂度为O(n^2)

具体过程见下图和表

C++代码如下：

 #include<stdio.h>
 #define MAXDIS 4294967295
 using namespace std; class MatrixGraphic{
 public:
     MatrxiGraphic(int number=){
         this->vertexNum = number;
         vertex = new int[vertexNum];
         arc = new int *[vertexNum];
         for(int i=;i<vertexNum;i++)
         {
             arc[i]=new int[vertex];
             for(int j=;j<vertexNum;j++)
             {
                 arc[i][j] = MAXDIS;
             }
         }
     }     int getValueOfEdge(int start,int end)
     {
         return arc[start][end];j
     }
     int getVertexNumber()
     {
         return vertexNum;
     }     void setValueOfEdge(int start,int end,int value)
     {
         this->arc[start][end] = value;
     }
 private:
     int vertexNum;
     int *vertex;
     int **arc;
 } void dijkstra(MatrixGraphic *graphic,int s,int *dist,int *prev)
 {
     int vertexNUm = graphic->getVertexNumber();
     bool *S = new bool[vertexNum];
     for(int i=;i<vertexNum;i++)
     {
         dist[i]=graphic->getValueOfEdge(s,i);
         S[i]=false;
         if(dist[i]==MAXDIS)
         {
             prev[i]=-;
         }
         else
         {
             prev[i]=s;
         }
     }     dist[s]=;
     S[s] = true;     for(int i=;i<vertexNum;i++)
     {
         int temp = MAXDIS;
         int u=s;
         for(int j=;j<vertexNum;j++)
         {
             if(!S[j] && dist[j]<temp)
             {
                 u=j;
                 temp = dist[j];
             }
         }
         S[u]=true;
         for(int j=;j<vertexNum;j++)
         {
             int edge = graphic->getValueOfEdge(u,j);
             if(!S[i] && edge<MAXDIS)
             {
                 int newDist = dist[u]+edge;
                 if(newDist<dist[j])
                 {
                     dist[j]=newDist;
                     prev[j]=u;
                 }
             }
         }
     }     for(int i=;i<vertexNum;i++)
     {
         int *stack = new int[vertexNum];
         int top = ;
         stack[top]=i;
         top++;
         int tempVertex = prev[i];
         while(tempVertex != s)
         {
             stack[top]=tempVertex;
             top++;
             tempVertex = prev[tempVertex];
         }
         stack[top] = s;
         for(int j=top;j>=;j--)
         {
             if(j!=)
             {
                 cout<<stack[top]<<"->";
             }
             else
             {
                 cout<<stack[top]<<endl;
             }
         }
     }
 }