图之Dijkstra算法 (一)

c语言实现如下：（使用邻接矩阵存储）

#include   
#include   
#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 edgeva lue);

int main(void){  
		//动态创建存放边的二维数组 
        int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);  
        int i,j;  
        for(i=0;iNULL
			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;ivertex,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;ivertex = startVertex;
			e->value = 0;
			e->next = NULL;
			(*path)[i] = e;
		}else{
            (*path)[i] = NULL;
		}
    }
	//初始化最短路径的权值
	*shortestPath = (int *)malloc(sizeof(int)*VERTEXNUM);
	for(i=0;i							start = i;  
                                                        end = j;  
                                                }  
                                        }  
                                }  
                        }  
                }  
                vNum++;  
			//将点设置为访问过 
			vertexStatusArr[end] = 1;   
			//保存最短路径权值
			(*shortestPath)[end] = shortest;
			//保存最短路径
			createPath(*path, startVertex, start, end, edgeva lue); 
        }  
}

//返回从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 edgeva lue){
	if(start == startVertex){
		st_edge* newEdge = (st_edge*)malloc(sizeof(st_edge));
		newEdge->vertex = end;
		newEdge->value = edgeva lue;
		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;
			*pC