单源最短路Dijstra算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Dijstra算法是寻找从某一顶点i出发到大其他顶点的最短路径。Distra算法的思想与Prim算法很像，它收录顶点的规则是按照路径长度递增的顺序收录的。设v0是源顶点，我们要寻找从v0出发到其他任意一点的最短路径。设已经求解的顶点(已经找到从v0出发到达该顶点最短路径的顶点)组成的集合是S={v0,v1,...vk};在收录下一个顶点v的时候要么是(v0,v),要么是(v0,vj,v);如果是后者，则一定有vj∈S,这一点很容易用反正法证明。Dijstra算法的时间复杂度是O(V^2),若是稀疏图改用邻接表存储，使用最小堆时间复杂度是O(ElogV).具体代码如下(这里假设图是连通的)，有相应的解释：

 #include<iostream>

 using namespace std;

 #define MAX_SIZE 100

 #define MAX_NUMBER INT_MAX/2

 struct Graph {

   int V, E;

   int w[MAX_SIZE][MAX_SIZE];

 };

 bool visit[MAX_SIZE];

 int dis[MAX_SIZE];

 int parent[MAX_SIZE];

 void Dijstra(Graph G, int i);     //顶点i为出发点到其他点最短距离

 void PrintPath(int j);

 int main() {

     int i, j,w,k;

     Graph G;

     for (i = ; i < MAX_SIZE; i++)

     for (j = ; j < MAX_SIZE; j++)

         G.w[i][j] = (i == j ?  :MAX_NUMBER);        //对角线设置为0，其它设置为无穷

     cin >> G.V >> G.E;

     for (k=; k< G.E; k++) {

         cin >> i >> j >> w;

         G.w[i][j] = G.w[j][i]=w;

     }

     Dijstra( G, );

     for (i = ; i < G.V; i++)

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

     PrintPath();           //打印顶点6的路径

     return ;

 }

 void Dijstra(Graph G, int i) {

     int k, j,pos,min;

     memset(visit, , sizeof(visit));     //初始化

     for (j = ; j < G.V; j++)

         dis[j] = MAX_NUMBER;               //首先将距离都设置为无穷大

     j = i;

     dis[j] = ;                 //到自身距离为0

     parent[j] = -;            //i是父节点

     visit[j] = ;             //首先将顶点i本身收录

     for (i = ; i < G.V; i++) {

         for (k = ; k < G.V; k++) {     //更新上次收录的顶点j对其他顶点的影响

             if (!visit[k] && dis[k]>=dis[j] + G.w[j][k]) {//这里G.w[j][k]在之前初始化不要设置为INT_MAX,否则dis[j]+G.w[j][k]

                 //可能会超过int的范围。

                 dis[k] = dis[j] + G.w[j][k];

                 parent[k] = j;

             }

         }

         pos = j, min =MAX_NUMBER;

         for (k = ; k < G.V; k++) {

             if (!visit[k] && min>dis[k]) {

                 pos = k;

                 min = dis[k];

             }

         }

         j = pos;

         visit[j] = ;  //将j收录

     }

 }

 void PrintPath(int j) {

     if (j== -)

         return;

     PrintPath(parent[j]);

     printf("%d  ", j);

 }