提示：部分内容我设置了隐藏，点赞之后会自动显示



仅供借鉴参考，请勿抄袭



有不足的地方希望大佬能为我指出

依然是这周数据结构的ddl，这周的作业真的是太舒服了，一会儿就结束了
正好昨天刚买了一本科幻小说集可以有时间看了
nice

原题：

我遇到的问题

1.我定义了好几个数组用来记录目前的最短路径的数据，包括长度等，
实际上可以定义一个结构来记录，会比较清楚，不至于像我一样定义一堆变量和数组
2.再刷新权值信息时，一定要注意判断条件：
包括权值的比较，这个节点是否已被找到等，不然结果错的很诡异qaq
3.循环一轮之后最小值要刷新。

实现代码：

头文件 宏和结构的定义

#include<stdio.h>
#include<stdlib.h>
#define MAX_VER_TEX 20//定点的最大个数 
#define VertexType int 
#define ERROR -1
#define OK 0
#define MAX 10000
//typedef enum
//{	Digraph,//有向图 
//	Undigraph//无向图 
//}GraphKind;
typedef struct ArcNode{//弧结点结构 
	int adjvex;//本弧指向的结点的位置
	struct ArcNode *nextarc;//指向下一个弧的指针
	int weight;//权值 
}ArcNode;

typedef struct VNode{//定点结构
	VertexType data; //储存结点的信息 
	ArcNode* firstarc;//指向第一条弧的指针 
}VNode,AdjList[MAX_VER_TEX];
typedef struct{	//图的结构
	AdjList vertexs;//储存顶点的数组
	int vexnum;//顶点个数 
	int arcnum;//边的个数
	//GraphKind kind;//图的种类  
}ALGraph;

有向图操作相关子函数

	int Locate(ALGraph g,VertexType elem)//定位这个结点在数组中的位置
{	int i;
	for(i=0;i<g.vexnum;i++)
	{	if(elem==g.vertexs[i].data)
		return i; 
	}
	return ERROR;//找不到对应元素，返回-1表示不存在 
}
int CreateAlgraph(ALGraph *g)//输入图结构，图的顶点个数，边个数
{	
	int i;
	int a,b,c,pa,pb;
	ArcNode* p;
	printf("输入图的有关信息，\n输入格式：图顶点个数+空格+边个数\n");
	scanf("%d %d",&(g->vexnum),&(g->arcnum));
	printf("下面请输入第一个顶点信息：");
	for(i=0;i<g->vexnum;i++)
	{	scanf("%d",&g->vertexs[i].data);
		g->vertexs[i].firstarc=NULL;
		if(i!=g->vexnum-1)
		{	printf("请输入下一个结点的信息：");
		}
	}
	printf("下面输入第一条边的信息，\n输入格式：起点的信息+空格+终点的信息+权值\n");
	for(i=0;i<g->arcnum;i++)
	{	scanf("%d %d %d",&a,&b,&c);
		pa=Locate(*g,a);//起点在数组里的位置 
		pb=Locate(*g,b);//终点在数组里的位置
		if(pa<0||pb<0)
		{	printf("这个边并不存在，请重新输入\n");
			i--;
			continue; 
		}
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=pb;
		p->weight=c;
		//下面把这个边信息插到起点的弧信息的第一个 
		p->nextarc=g->vertexs[pa].firstarc;
		g->vertexs[pa].firstarc=p;
		if(i!=g->arcnum-1)
		printf("请输入下一条边的信息："); 
		
	}
} 
void PrintOutAlgraph(ALGraph g)
{	int i,j=1;
	ArcNode *p;
	printf("\n*---------分割线---------*\n");
	printf("这个图共有%d个顶点%d条边:\n",g.vexnum,g.arcnum); 
	printf("这个图的顶点信息：\n");
	for(i=0;i<g.vexnum;i++)
	{	printf("该图结构的第%d个顶点的信息是%d\n",i+1,g.vertexs[i].data);
	}
	printf("这个图的边信息：\n");
	for(i=0;i<g.vexnum;i++)
	{	p=g.vertexs[i].firstarc;
		while(p)
		{	printf("第%d条边:（%d ,%d) 权值为：%d\n",j,g.vertexs[i].data,g.vertexs[p->adjvex].data,p->weight);
			j++;
			p=p->nextarc;
		}
	 }
	printf("*---------分割线---------*\n");  
}
//插入一个顶点，返回顶点在图数组里的位置，如果该顶点已经存在，或者数组已满返回-1; 
int InsertArc(ALGraph *g,int a,int b,int aweight)
{	int pa,pb;
	ArcNode*p;
		pa=Locate(*g,a);//起点在数组里的位置 
		pb=Locate(*g,b);//终点在数组里的位置
		if(pa<0||pb<0)
		{	printf("这个边并不存在，请重新输入\n");
			return ERROR;
		}
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=pb;
		p->weight=aweight;
		//下面把这个边信息插到起点的弧信息的第一个 
		p->nextarc=g->vertexs[pa].firstarc;
		g->vertexs[pa].firstarc=p;
		g->arcnum++;//边个数增加 
		return OK;
}
int DeleteArc(ALGraph *g,int a,int b)
{	int pa,pb;
	ArcNode *p,*temp;
	pa=Locate(*g,a);//起点在数组里的位置 
	pb=Locate(*g,b);//终点在数组里的位置
	if(pa<0||pb<0)
		return ERROR;
	p=g->vertexs[pa].firstarc;
	if(p->adjvex==pb)//p为头结点的情况 
		 {	temp=p;
		 	free(temp);
		 	g->vertexs[pa].firstarc=p->nextarc;
		 }

	while(p->nextarc!=NULL)
		{	if(p->nextarc->adjvex==pb)
			{	temp=p->nextarc;
				p->nextarc=temp->nextarc;	
				free(temp);
				break;
			}			
			p=p->nextarc;
		}
	g->arcnum--;//边个数减一 
	return OK;
		 
 } 
int InsertVex(ALGraph *g,int adata)
{	int i;
	if(g->vexnum==MAX_VER_TEX)
	return ERROR;
	for(i=0;i<g->vexnum;i++)
	{	if(adata==g->vertexs[i].data)
		return ERROR;
	}
	g->vertexs[g->vexnum].data=adata;
	g->vertexs[g->vexnum].firstarc=NULL;
	g->vexnum++;//顶点个数增加 
	return g->vexnum-1;
}
int Delete(ArcNode *p)//删除顶点的辅助函数：递归调用删除弧结点内容 
{	if(p)
	{
		Delete(p->nextarc);
		free(p);
		return OK;
	}
	else 
		return NULL;
}
int DeleteVex(ALGraph *g,VertexType adata)
{	int qq=0;
	ArcNode *p,*del,*pre;
	int pdata=Locate(*g,adata);//定位结点位置 
	if(pdata<0)//结点不存在，返回错误信息 
	return ERROR;
	//Delete(g->vertexs[pdata].firstarc);//删除这个结点储存的弧信息
	p=g->vertexs[pdata].firstarc;
	while(p)
	{	g->arcnum--;
		p=p->nextarc;
	 } 
	int i;
	for(i=pdata;i<g->vexnum-1;i++)//数组内容移位 
	{	g->vertexs[i].data=g->vertexs[i+1].data;
		g->vertexs[i].firstarc=g->vertexs[i+1].firstarc;//顶点信息和第一条弧的指针都移位 
	}
	g->vertexs[g->vexnum-1].data=-1;
	g->vertexs[g->vexnum-1].firstarc=NULL;
	g->vexnum--;//顶点个数减1 
	for(i=0;i<g->vexnum;i++)
	{	p=g->vertexs[i].firstarc;
		while(p)
		{	if(p->adjvex==pdata)
			{	
				if(p==g->vertexs[i].firstarc)
				{	del=p;
					p=p->nextarc;
					g->vertexs[i].firstarc=p;
					pre=NULL;
					free(del);
					g->arcnum--;
					break;
				}
				else
				{	del=p;
					p=p->nextarc;
					pre->nextarc=p;
					free(del);
					g->arcnum--;
					break;
				}
			}
			else if(p->adjvex>pdata)
			{	p->adjvex--;
			}
			pre=p;
			p=p->nextarc;
		}
		
	}
	return OK; 
}
int GetWeight(ALGraph g,VertexType a,VertexType b )//获取权值 
{	int pa,pb;
	pa=Locate(g,a);
	pb=Locate(g,b);
	ArcNode* p;
	p=g.vertexs[pa].firstarc;
	while(p!=NULL)
	{	if(p->adjvex==pb)
		return p->weight;
		else
		p=p->nextarc;
	}
	return -1;
}

Dijkstra算法函数

void Dijkstra(ALGraph g,VertexType start)
{	int i,j,min,minnum,pa;
	int sumweight[g.vexnum];//目前起始点到该点路径的权值和 
	int lastroad[g.vexnum];//当前最短路径 
	int lastnum; //当前最短路径长度
	int lastweight=0;//当前最短路径权值 
	int judge[g.vexnum]={0};//判断该点是否已经找到路径 
	sumweight[pa]=0;
	lastroad[0]=start;
	 
	//初始化操作 
	pa=Locate(g,start); 
	lastnum=1;
	lastroad[0]=start;
	judge[pa]=1;
	for(i=0;i<g.vexnum;i++)
	{	if(judge[i]==1)//已经找到 
		continue;
		sumweight[i]=lastweight+GetWeight(g,start,g.vertexs[i].data);//刷新权值表 
	}

for(j=1;j<g.vexnum;j++)	
{
	min=MAX;
	for(i=0;i<g.vexnum;i++)
	{	if(sumweight[i]>0&&judge[i]==0&&sumweight[i]<min)
			{	min=sumweight[i];//找到权值最小 
				minnum=i; //权值最小的位置 
			}	
	}
	//向最短路径数组中增加 
	printf("%d-->%d：",lastroad[0],g.vertexs[minnum].data);
	for(i=0;i<lastnum;i++)
	{
		printf("%d--->",lastroad[i]);
	}
	printf("%d 总权值为%d\n",g.vertexs[minnum].data,sumweight[minnum]);
	judge[minnum]=1;
	lastroad[lastnum]=g.vertexs[minnum].data;
	lastweight=sumweight[minnum]; 
	lastnum++;
	start=g.vertexs[minnum].data;
	for(i=0;i<g.vexnum;i++)
	{	if(judge[i]==1)//已经找到 
		continue;
		if(GetWeight(g,start,g.vertexs[i].data)!=-1&&(GetWeight(g,start,g.vertexs[i].data)+lastweight<sumweight[i]||sumweight[i]==-1))
		sumweight[i]=lastweight+GetWeight(g,start,g.vertexs[i].data);//刷新权值表 
	}
}
}

测试函数

int main()
{	ALGraph test;
	CreateAlgraph(&test);
	PrintOutAlgraph(test);
	Dijkstra(test,1);
	
}

输入和输出

相关数据：

最后测试的数据我采用了课件上的一个强连通图

输入大家自行输入，
也可用我的：5 7 1 2 3 4 5 1 2 10 2 3 50 4 3 20 5 4 60 1 5 100 3 5 10 1 	4 30

输出结果：