当前位置：编程学习 > C/C++ >>

图之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
补充：软件开发 , C++ ,

上一个：hdu1238 Substrings (暴力)
下一个：hdu1072 Nightmare (BFS)

更多图片编程知识:
更多C/C++疑问解答：
关于c++的cout输出的问题。
在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
全国计算机二级C语言笔试题
已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
c++数据结构内部排序问题，整数排序
2012九月计算机二级C语言全国题库，，急求急求
如果assert只有一个字符串作为参数，是什么意思呢?
C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
为什么用结构体编写的程序输入是，0输不出来啊~~~
将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
为什么这个程序求不出公式？
这个链表倒置的算法请大家分析下
c语言函数库调用
C语言unsigned int纠错
C语言快排求解啊
asp
php
Delphi
Matlab
JSP
Foxpro
JS
C/C++
C#/ASP.NET
VC++
JAVA
VB
汇编语言
html/css
CGI
XML/UML
wap
网站相关
网页素材
python
微信小程序
thinkphp
如果你遇到编程学习难题：
访问www.zzzyk.com 试试
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，