图之Dijkstra算法

aaaaa 8年前

来自: http://blog.csdn.net/todd911/article/details/9347053


Dijkstra算法是一种求单源最短路算法,即从一个点开始到所有其他点的最短路。其步骤如下:













c语言实现如下:(使用邻接矩阵存储)

#include <stdio.h>    #include <malloc.h>    #define VERTEXNUM 6      //存放最短路径的边元素  typedef struct edge{          int vertex;    int value;          struct edge* next;  }st_edge;    void createGraph(int (*edge)[VERTEXNUM], int start, int end, int value);    void displayGraph(int (*edge)[VERTEXNUM]);   void displayPath(st_edge** path, int startVertex,int* shortestPath);  void dijkstra(int (*edge)[VERTEXNUM], st_edge*** path, int** shortestPath, int startVertex, int* vertexStatusArr);  int getDistance(int value, int startVertex, int start, int* shortestPath);  void createPath(st_edge **path, int startVertex, int start, int end, int edgeValue);    int main(void){      //动态创建存放边的二维数组           int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);            int i,j;            for(i=0;i<VERTEXNUM;i++){                    for(j=0;j<VERTEXNUM;j++){                            edge[i][j] = 0;                    }            }      //存放顶点的遍历状态,0:未遍历,1:已遍历          int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);            for(i=0;i<VERTEXNUM;i++){                    vertexStatusArr[i] = 0;            }                printf("after init:\n");            displayGraph(edge);      //创建图           createGraph(edge,0,1,6);            createGraph(edge,0,3,5);            createGraph(edge,0,2,1);            createGraph(edge,1,2,5);            createGraph(edge,1,4,3);            createGraph(edge,2,4,6);            createGraph(edge,2,3,5);            createGraph(edge,2,5,4);            createGraph(edge,3,5,2);            createGraph(edge,4,5,6);                printf("after create:\n");            displayGraph(edge);   //最短路径    /*存储的结构如下:     path[0]:edge0->NULL     path[1]:edge1->NULL     path[2]:edge1->edge2->NULL     path[3]:edge1->edge2->edge3->NULL     path[4]:edge4->NULL     从顶点0到0的最短路径:从0出发直接到0     从顶点0到1的最短路径:从0出发直接到1     从顶点0到2的最短路径:从0出发到1,从1出发到2     ......    */   st_edge** path = NULL;   //存储最短路径的权值    /*    shortestPath[0] = 0;    shortestPath[1] = 8;    shortestPath[2] = 12;    从顶点0到0的路径是0    从顶点0到1的路径是8    从顶点0到2的路径是12    */   int* shortestPath = NULL;   //从顶点0开始寻找最短路径   int startVertex = 0;   //最短路径   dijkstra(edge, &path, &shortestPath, startVertex, vertexStatusArr);   printf("the path is:\n");   displayPath(path,startVertex,shortestPath);              free(edge);            free(path);            return 0;    }    //创建图   void createGraph(int (*edge)[VERTEXNUM], int start, int end, int value){            edge[start][end] = value;            edge[end][start] = value;    }    //打印存储的图  void displayGraph(int (*edge)[VERTEXNUM]){            int i,j;            for(i=0;i<VERTEXNUM;i++){                    for(j=0;j<VERTEXNUM;j++){                            printf("%d ",edge[i][j]);                    }                    printf("\n");            }    }  //打印最短路径  void displayPath(st_edge** path, int startVertex,int* shortestPath){          int i;          st_edge* p;          for(i=0;i<VERTEXNUM;i++){                  printf("Path from %d to %d:",startVertex,i);                  p = *(path+i);                  while(p != NULL){                          printf("%d(%d) ",p->vertex,p->value);                          p = p->next;                  }                  printf("\n");    printf("the count is:%d\n",shortestPath[i]);          }  }  //最短路径  void dijkstra(int (*edge)[VERTEXNUM], st_edge*** path, int** shortestPath, int startVertex, int* vertexStatusArr){   //初始化最短路径   *path = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);          int i,j;      for(i=0;i<VERTEXNUM;i++){    if(i == startVertex){     st_edge* e = (st_edge*)malloc(sizeof(st_edge));     e->vertex = startVertex;     e->value = 0;     e->next = NULL;     (*path)[i] = e;    }else{              (*path)[i] = NULL;    }      }   //初始化最短路径的权值   *shortestPath = (int *)malloc(sizeof(int)*VERTEXNUM);   for(i=0;i<VERTEXNUM;i++){    if(i == startVertex){     (*shortestPath)[i] = 0;    }else{     (*shortestPath)[i] = -1;    }   }   //从顶点0开始,则顶点0就是已访问的    vertexStatusArr[startVertex] = 1;           int shortest, distance,start, end, edgeValue, vNum = 1;    //如果还顶点还没有访问完          while(vNum < VERTEXNUM){                  shortest = 9999;                    for(i=0;i<VERTEXNUM;i++){          //选择已经访问过的点                          if(vertexStatusArr[i] == 1){                                    for(j=0;j<VERTEXNUM;j++){              //选择一个没有访问过的点                                            if(vertexStatusArr[j] == 0){                //选出一条value最小的边                                                  if(edge[i][j] != 0 && (distance = getDistance(edge[i][j], startVertex, i,  *shortestPath)) < shortest){                                                            shortest = distance;                                                            edgeValue = edge[i][j];         start = i;                                                            end = j;                                                    }                                            }                                    }                            }                    }                    vNum++;       //将点设置为访问过      vertexStatusArr[end] = 1;        //保存最短路径权值     (*shortestPath)[end] = shortest;     //保存最短路径     createPath(*path, startVertex, start, end, edgeValue);           }    }    //返回从startVertex到新的顶点的距离  int getDistance(int value, int startVertex, int start, int* shortestPath){   if(start == startVertex){    return value;   }else{    return shortestPath[start] + value;   }  }    //保存最短路径  void createPath(st_edge **path, int startVertex, int start, int end, int edgeValue){   if(start == startVertex){    st_edge* newEdge = (st_edge*)malloc(sizeof(st_edge));    newEdge->vertex = end;    newEdge->value = edgeValue;    newEdge->next = NULL;        st_edge** p = path + end;    while((*p) != NULL){     p = &((*p)->next);    }    *p = newEdge;   }else{    st_edge** pCopySrc = path + start;    st_edge** pCopyDes = path + end;    st_edge* newEdge = NULL;    while((*pCopySrc) != NULL){     newEdge = (st_edge*)malloc(sizeof(st_edge));     *newEdge = **pCopySrc;     newEdge->next = NULL;     *pCopyDes = newEdge;     pCopySrc = &((*pCopySrc)->next);     pCopyDes = &((*pCopyDes)->next);    }    newEdge = (st_edge*)malloc(sizeof(st_edge));    newEdge->vertex = end;    newEdge->value = edgeValue;    newEdge->next = NULL;    *pCopyDes = newEdge;   }  }


c语言实现如下:(使用邻接表存储)

#include <stdio.h>  #include <malloc.h>  #define VERTEXNUM 6    //存放顶点的邻接表元素  //存放最短路径的边元素  typedef struct edge{          int vertex;    int value;          struct edge* next;  }st_edge;    void createGraph(st_edge** edge, int start, int end, int value);  void displayGraph(st_edge** edge);  void delGraph(st_edge** edge);  void dijkstra(st_edge** edge, st_edge*** path, int** shortestPath, int startVertex, int* vertexStatusArr);  void displayPath(st_edge** path, int startVertex,int* shortestPath);  int getDistance(int value, int startVertex, int start, int* shortestPath);  void createPath(st_edge **path, int startVertex, int start, int end, int edgeValue);    int main(void){   //动态创建存放边的指针数组     st_edge** edge = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);   int i;   for(i=0;i<VERTEXNUM;i++){     edge[i] = NULL;   }   //存放顶点的遍历状态,0:未遍历,1:已遍历   int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);   for(i=0;i<VERTEXNUM;i++){     vertexStatusArr[i] = 0;   }     printf("after init:\n");   displayGraph(edge);   //创建图   createGraph(edge,0,1,6);   createGraph(edge,0,3,5);   createGraph(edge,0,2,1);   createGraph(edge,1,2,5);   createGraph(edge,1,4,3);   createGraph(edge,2,4,6);   createGraph(edge,2,3,5);   createGraph(edge,2,5,4);   createGraph(edge,3,5,2);   createGraph(edge,4,5,6);     printf("after create:\n");   displayGraph(edge);     //最短路径   /*存储的结构如下:    path[0]:edge0->NULL    path[1]:edge1->NULL    path[2]:edge1->edge2->NULL    path[3]:edge1->edge2->edge3->NULL    path[4]:edge4->NULL    从顶点0到0的最短路径:从0出发直接到0    从顶点0到1的最短路径:从0出发直接到1    从顶点0到2的最短路径:从0出发到1,从1出发到2    ......   */   st_edge** path = NULL;   //存储最短路径的权值   /*   shortestPath[0] = 0;   shortestPath[1] = 8;   shortestPath[2] = 12;   从顶点0到0的路径是0   从顶点0到1的路径是8   从顶点0到2的路径是12   */   int* shortestPath = NULL;   int startVertex = 0;   //最短路径   dijkstra(edge, &path, &shortestPath, startVertex, vertexStatusArr);   printf("the path is:\n");   displayPath(path,startVertex,shortestPath);     delGraph(edge);   edge = NULL;     delGraph(path);    path = NULL;      if(vertexStatusArr != NULL){           free(vertexStatusArr);           vertexStatusArr = NULL;   }     if(shortestPath != NULL){    free(shortestPath);    shortestPath = NULL;   }          return 0;  }  //创建图  void createGraph(st_edge** edge, int start, int end, int value){          st_edge* newedge1 = (st_edge*)malloc(sizeof(st_edge));          newedge1->vertex = end;   newedge1->value = value;          newedge1->next = NULL;          st_edge** edge1 = edge + start;          while(*edge1 != NULL){                  edge1 = &((*edge1)->next);          }          *edge1 = newedge1;     st_edge* newedge2 = (st_edge*)malloc(sizeof(st_edge));          newedge2->vertex = start;          newedge2->value = value;          newedge2->next = NULL;          st_edge** edge2 = edge + end;          while(*edge2 != NULL){                  edge2 = &((*edge2)->next);          }          *edge2 = newedge2;  }  //打印存储的图    void displayGraph(st_edge** edge){          int i;          st_edge* p;          for(i=0;i<VERTEXNUM;i++){                  printf("%d:",i);                  p = *(edge+i);                  while(p != NULL){                          printf("%d(%d) ",p->vertex,p->value);                          p = p->next;                  }                  printf("\n");          }  }  //打印最短路径  void displayPath(st_edge** path, int startVertex,int* shortestPath){          int i;          st_edge* p;          for(i=0;i<VERTEXNUM;i++){                  printf("Path from %d to %d:",startVertex,i);                  p = *(path+i);                  while(p != NULL){                          printf("%d(%d) ",p->vertex,p->value);                          p = p->next;                  }                  printf("\n");    printf("the count is:%d\n",shortestPath[i]);          }  }  //释放邻接表占用的内存  void delGraph(st_edge** edge){          int i;          st_edge* p;          st_edge* del;          for(i=0;i<VERTEXNUM;i++){                  p = *(edge+i);                  while(p != NULL){                          del = p;                          p = p->next;                          free(del);                  }                  edge[i] = NULL;          }          free(edge);  }  //dijkstra求最短路径  void dijkstra(st_edge** edge, st_edge*** path, int** shortestPath, int startVertex, int* vertexStatusArr){   //初始化最短路径   *path = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);          int i,j;          for(i=0;i<VERTEXNUM;i++){    if(i == startVertex){     st_edge* e = (st_edge*)malloc(sizeof(st_edge));     e->vertex = startVertex;     e->value = 0;     e->next = NULL;     (*path)[i] = e;    }else{              (*path)[i] = NULL;    }          }   //初始化最短路径的权值   *shortestPath = (int *)malloc(sizeof(int)*VERTEXNUM);   for(i=0;i<VERTEXNUM;i++){    if(i == startVertex){     (*shortestPath)[i] = 0;    }else{     (*shortestPath)[i] = -1;    }   }     vertexStatusArr[startVertex] = 1;     st_edge* p;   int shortest, distance, edgeValue, start, end, vNum = 1;   //如果还顶点还没有访问完   while(vNum < VERTEXNUM){    shortest = 9999;    for(i=0;i<VERTEXNUM;i++){     //选择已经访问过的点     if(vertexStatusArr[i] == 1){      for(j=0;j<VERTEXNUM;j++){       //选择一个没有访问过的点        if(vertexStatusArr[j] == 0){        p = *(edge+i);        while(p != NULL){         //如果从startVertex到j的距离小于shortest         if((distance = getDistance(p->value, startVertex, i, *shortestPath)) < shortest && p->vertex == j){          shortest = distance;          edgeValue = p->value;          start = i;          end = j;         }         p = p->next;        }             }      }     }    }    vNum++;    vertexStatusArr[end] = 1;    //保存最短路径的权值    (*shortestPath)[end] = shortest;    //保存最短路径    createPath(*path, startVertex, start, end, edgeValue);   }  }  //返回从startVertex到新的顶点的距离  int getDistance(int value, int startVertex, int start, int* shortestPath){   if(start == startVertex){    return value;   }else{    return value + shortestPath[start];   }  }  //保存最短路径  void createPath(st_edge **path, int startVertex, int start, int end, int edgeValue){   if(start == startVertex){    st_edge* newEdge = (st_edge*)malloc(sizeof(st_edge));    newEdge->vertex = end;    newEdge->value = edgeValue;    newEdge->next = NULL;        st_edge** p = path + end;    while((*p) != NULL){     p = &((*p)->next);    }    *p = newEdge;   }else{    st_edge** pCopySrc = path + start;    st_edge** pCopyDes = path + end;    st_edge* newEdge = NULL;    while((*pCopySrc) != NULL){     newEdge = (st_edge*)malloc(sizeof(st_edge));     *newEdge = **pCopySrc;     newEdge->next = NULL;     *pCopyDes = newEdge;     pCopySrc = &((*pCopySrc)->next);     pCopyDes = &((*pCopyDes)->next);    }    newEdge = (st_edge*)malloc(sizeof(st_edge));    newEdge->vertex = end;    newEdge->value = edgeValue;    newEdge->next = NULL;    *pCopyDes = newEdge;   }  }