圖之Dijkstra算法

aaaaa 8年前發布 | 27K 次閱讀算法

來自： 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;
    }
}

本文由用戶 aaaaa 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1455498389401.html

算法

圖之Dijkstra算法

相關經驗

相關資訊

相關文檔

目錄