图之有权最短路径-迪杰斯特拉

采用邻接矩阵表示图，5点有权图如下：

//main函数入口

#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAXSIZE 20#define INFINITY 65535typedef char VertexType;typedef struct Graph  //邻接矩阵表示法{	VertexType ver[MAXSIZE+1];	int edge[MAXSIZE][MAXSIZE];}Graph;void CreateGraph(Graph *g){	int i=0;	int j=0;	int VertexNum;	VertexType Ver;	PRintf("please input the vertex of graph:/n");	while('/n'!=(Ver=getchar()))		g->ver[i++]=Ver;	g->ver[i]='/0';	VertexNum=strlen(g->ver);	printf("input adjacency matrix of matrix:/n");	for(i=0;i<VertexNum;i++)	{		for(j=0;j<VertexNum;j++)			scanf("%d",&g->edge[i][j]);	}}void PrintGraph(Graph G){	int i,j;	int VertexNum=strlen(G.ver);	printf("vertex of graph:/n");	for(i=0;i<VertexNum;i++)		printf("%c",G.ver[i]);	printf("/n");	printf("adjacency matrix of graph:/n");	for(i=0;i<VertexNum;i++)	{		for(j=0;j<VertexNum;j++)			printf("%d",G.edge[i][j]);		printf("/n");	}}int CalVerNum(Graph G){	return strlen(G.ver);}void SetWeight(Graph *g)  //不邻接点设置无穷大{	int i,j;	for(i=0;i<CalVerNum(*g);i++)		for(j=0;j<CalVerNum(*g);j++)		{			if(0==g->edge[i][j])				g->edge[i][j]=INFINITY;		}}void Dijkstra(Graph g,int first,int end){	int VertexNum=CalVerNum(g);	int i,j,k,mini;	int *used=(int *)malloc(sizeof(int)*VertexNum);  //动态申请内存 由于数组小标必须为常量 这里为变量	int *distance=(int *)malloc(sizeof(int)*VertexNum);	int *parent=(int *)malloc(sizeof(int)*VertexNum);	SetWeight(&g);	for(i=0;i<VertexNum;i++)	{		used[i]=0;		distance[i]=g.edge[0][i];		parent[i]=0;	}	used[0]=1;	for(i=0;i<VertexNum-1;i++)	{		j=0;		mini=INFINITY;		for(k=0;k<VertexNum;k++)			if((0==used[k])&&(distance[k]<mini))			{				mini=distance[k];				j=k;			}		used[j]=1;		for(k=0;k<VertexNum;k++)			if((0==used[k])&&(distance[k]>distance[j]+g.edge[j][k]))			{				distance[k]=distance[j]+g.edge[j][k];				parent[k]=j; //路径求并			}	}	printf("%c to %c the least path:/n",g.ver[first],g.ver[end]);	i=end;	while(parent[i]!=0)	{		printf("%c",g.ver[parent[i]]);		i=parent[i];	}	printf("/n");	printf("length of the least path:%d/n",mini);	free(used);	free(distance);	free(parent);}int main(void){	int i,j;	Graph g;	CreateGraph(&g);	PrintGraph(g);	printf("please enter first and end number:/n");//输入起点和终点的顶点序号	scanf("%d %d",&i,&j);	Dijkstra(g,i,j);	return 0;}
运行测试结果如下：