圖之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];
<SPAN style="WHITE-SPACE: pre">							</SPAN>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;
	}
}

#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;
	}
}