图之Dijkstra算法 - c++编程基础

opyDes = newEdge; pCopySrc = &((*pCopySrc)->next); pCopyDes = &((*pCopyDes)->next); } newEdge = (st_edge*)malloc(sizeof(st_edge)); newEdge->vertex = end; newEdge->value = edgeva lue; newEdge->next = NULL; *pCopyDes = newEdge; } }
#include 
#include 
#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 edgeva lue);

int main(void){
	//动态创建存放边的指针数组  
	st_edge** edge = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);
	int i;
	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;
	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;ivertex,p->value);
                        p = p->next;
                }
                printf("\n");
        }
}
//打印最短路径
void displayPath(st_edge** path, int startVertex,int* shortestPath){
        int i;
        st_edge* p;
        for(i=0;ivertex,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;inext;
                        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;ivertex = startVertex;
			e->value = 0;
			e->next = NULL;
			(*path)[i] = e;
		}else{
            (
图之Dijkstra算法 (二)
