东莞网站设计,无聊网站建设,焊锡外发加工网,抖音代运营工作内容问题描述 将图以邻接矩阵或邻接表存储#xff0c;实现Dijkstra算法。
算法设计 迪杰斯特拉算法#xff1a;
1.假设用带权的邻接矩阵arc#xff0c;来表示带权有向图#xff0c;arc[i][j]#xff0c;表示弧vi,vj上的权值。若vi,vj不存在#xff0c;则置…问题描述 将图以邻接矩阵或邻接表存储实现Dijkstra算法。
算法设计 迪杰斯特拉算法
1.假设用带权的邻接矩阵arc来表示带权有向图arc[i][j]表示弧vi,vj上的权值。若vi,vj不存在则置arc[i][j]为无穷。 S为已找到从v出发的最短路径的终点的集合它的初始状态为空集。那么从v出发到图上其余各顶点可能达到的最短路径长度的初值为: D[j]arcs[LocateVex(G,v)][i] vi∈V
2.选择vj使得 D[j]Min{D[i]|vi∈V-S} vj就是当前求得的一条从v出发的最短路径的终点。令SS∪{j}
3.修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果 D[j]arcs[j][k]D[k] 则修改D[k]为D[k]D[j]arcs[j][k]
4.重复操作23共n-1次。 由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。 #includestdio.h
#includestring.h
#define INF 32767
#define MAXVEX 30
int dist[MAXVEX]; //建立dist数组int path[MAXVEX]; //建立path数组int S[MAXVEX]; //建立S数组typedef char VertexType;typedef struct graph
{int n,e;VertexType vexs[MAXVEX];int edges[MAXVEX][MAXVEX];
}MGraph;void CreateMGraph(MGraph G)
{int n,e;int value;char temp_i;char temp_j;printf(请输入图的顶点数和边数以空格分隔);scanf(%d%d,n,e);G.nn;G.ee;for(int i0;in;i){for(int j0;jn;j){if(ij)G.edges[i][j]0;elseG.edges[i][j]32767;}}printf(输入顶点信息);for(int j0;jG.n;j){getchar();scanf(%c,G.vexs[j]);}int temp_number_i;int temp_number_j;printf(请输入每条边的权值\n);for(int j0;je;j){getchar();scanf(%c %c %d,temp_i,temp_j,value);for(int i0;in;i){if(G.vexs[i]temp_i)temp_number_ii;if(G.vexs[i]temp_j)temp_number_ji;}G.edges[temp_number_i][temp_number_j]value;}}void DispMGraph(MGraph G)
{printf(输出顶点信息\n);for(int i0;iG.n;i){printf(%c,G.vexs[i]);} printf(\n输出邻接矩阵\n);printf(\t);for(int i0;iG.n;i)printf(%8c,G.vexs[i]); for(int i0;iG.n;i){printf(\n%8c,G.vexs[i]);for(int j0;jG.n;j){if(G.edges[i][j]32767) //两点之间无连接时权值为默认的32767// 在无向图中一般用0表示在有向图中一般用∞,// 这里为了方便统一输出 ∞printf(%8s, ∞);elseprintf(%8d,G.edges[i][j]);}printf(\n);}
}void Dijkstra(MGraph g, int v)
{ //求从v到其他顶点的最短路径int mindis,i,j,u0;for (i0;ig.n;i){ dist[i]g.edges[v][i]; //距离初始化S[i]0; //S[]置空if (g.edges[v][i]INF) //路径初始化path[i]v; //v→i有边时置i前一顶点为velse //v→i没边时置i前一顶点为-1path[i]-1;}S[v]1; //源点编号v放入S中for (i0;ig.n-1;i) //循环向S中添加n-1个顶点{ mindisINF; //mindis置最小长度初值for (j0;jg.n;j) //选取不在S中且有最小距离顶点uif (S[j]0 dist[j]mindis) { uj;mindisdist[j];}S[u]1; //顶点u加入S中for (j0;jg.n;j) //修改不在s中的顶点的距离if (S[j]0)if (g.edges[u][j]INF dist[u]g.edges[u][j]dist[j]){ dist[j]dist[u]g.edges[u][j];path[j]u;}}
}void Print(MGraph G,int v)
{printf(\n);for(int i0;iG.n;i){if(i!v dist[i]!INF){printf(%c到%c的最短距离为%d\n,G.vexs[v],G.vexs[i],dist[i]);}else if(dist[i]INF){printf(%c与%c之间无路径\n,G.vexs[v],G.vexs[i]); } }printf(\n);
}/*------------------输出从顶点v出发的所有最短路径-------------------*/
static void Dispath(MGraph g, int v)
{int i, j, k;int apath[MAXVEX], d; //存放一条最短路径(逆向)及其顶点个数//循环输出从顶点v到i的路径for(i 0; i g.n; i){if(S[i] 1 i ! v){printf(从顶点%c到顶点%c的路径长度为:%d\t路径为:, g.vexs[v], g.vexs[i], dist[i]);d 0; apath[d] i; //添加路径上的终点k path[i];if(k -1) //没有路径的情况printf(无路径\n);else //存在路径时输出该路径{while(k ! v){d;apath[d] k;k path[k];}d; apath[d] v; //添加路径上的起点printf(%c , g.vexs[apath[d]]); //先输出起点for(j d - 1; j 0; j--) //再输出其余顶点printf( %c , g.vexs[apath[j]]);printf(\n);}}}
}int main()
{MGraph G;CreateMGraph(G);DispMGraph(G);Dijkstra(G,0);Print(G,0);Dispath(G,0);
}
