int A[MAXV][MAXV],path[MAXV]
时间: 2023-11-30 15:25:51 浏览: 22
这段代码定义了一个二维数组 A 和一个一维数组 path,它们的长度最多为 MAXV。
二维数组 A 可以用来表示一个邻接矩阵,其中 A[i][j] 表示顶点 i 和顶点 j 之间是否有边相连。如果有,则 A[i][j] 的值为边的权重或者一个非零常数;如果没有,则 A[i][j] 的值为 0 或者一个特定的常数。
一维数组 path 可以用来存储从起点到终点的路径,其中 path[i] 表示从起点到顶点 i 经过的前一个顶点的编号。在求解最短路径等问题时,可以借助 path 数组来记录路径信息。
相关问题
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h> #define MAXV 1000 #define ElemType int #define INF 32767typedef struct { int no; int info; }VertexType; typedef struct{ int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV]; }
MGraph;
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("请输入顶点数和边数:\n");
scanf("%d,%d",&(G->n),&(G->e));
for(i=0;i<G->n;i++)
{
printf("请输入第%d个顶点的编号和信息:\n",i+1);
scanf("%d,%d",&(G->vexs[i].no),&(G->vexs[i].info));
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INF;
for(k=0;k<G->e;k++)
{
printf("请输入一条边的起点、终点和权值:\n");
scanf("%d,%d,%d",&i,&j,&w);
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}
void ShortestPath_Dijkstra(MGraph G,int v0,int *D,int *P)
{
int final[MAXV];
int i,j,k,min;
for(i=0;i<G.n;i++)
{
final[i]=0;
D[i]=G.edges[v0][i];
P[i]=0;
}
D[v0]=0;
final[v0]=1;
for(i=1;i<G.n;i++)
{
min=INF;
for(j=0;j<G.n;j++)
if(!final[j]&&D[j]<min)
{
k=j;
min=D[j];
}
final[k]=1;
for(j=0;j<G.n;j++)
if(!final[j] && (min+G.edges[k][j]<D[j]))
{
D[j]=min+G.edges[k][j];
P[j]=k;
}
}
}
void DisplayResult(MGraph G,int v0,int *D,int *P)
{
int i,j,k;
printf("起点为%d的最短路径如下:\n",v0);
for(i=0;i<G.n;i++)
{
if(i!=v0)
{
printf("从%d到%d的最短路径长度为:%d,路径为:",v0,i,D[i]);
j=i;
while(P[j]!=0)
{
printf("%d<-",G.vexs[j].no);
j=P[j];
}
printf("%d\n",G.vexs[j].no);
}
}
}
int main()
{
MGraph G;
int v0=0;
int D[MAXV],P[MAXV];
CreateMGraph(&G);
ShortestPath_Dijkstra(G,v0,D,P);
DisplayResult(G,v0,D,P);
return 0;
}
void Dispath(MatGraph g,int dist[],int path[],int s[],int v) { int apath[MAXV],d; int i,j,k; for(i=0;i<g.n;i++) { if(s[i]==1&&i!=v) { printf("从顶点%d到顶点%d的路径长度为:%d\t路径为:",v,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("%d",apath[d]); for(j=d-1;j>=0;j--) printf(",%d",apath[j]); printf("\n"); } } } } void Dijkstra(MatGraph g,int v) { int dist[MAXV]; int path[MAXV]; int s[MAXV]; int i,mindis,j,u; for(i=0;i<g.n;i++) { dist[i]=g.edges[v][i]; s[i]=0; if(g.edges[v][i]<INF) path[i]=v; else path[i]=-1; } s[v]=1; for(i=0;i<g.n-1;i++) { mindis=INF; for(j=0;j<g.n;j++) { if(s[j]==0&&dist[j]<mindis) { u=j; mindis=dist[j]; } } s[u]=1; for(j=0;j<g.n;j++) { 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; } } } } printf(" s数组值:"); for(i=0;i<g.n;i++) printf("%3d",s[i]); printf("\n"); printf("dist数组值:"); for(i=0;i<g.n;i++) printf("%3d",dist[i]); printf("\n"); printf("path数组值:"); for(i=0;i<g.n;i++) printf("%3d",path[i]); printf("\n"); printf("狄克斯特拉算法求解结果:\n"); Dispath(g,dist,path,s,v); }修改完善并给出代码
以下是修改完善后的 Dijkstra 算法代码:
```c
#include <stdio.h>
#define MAXV 100 // 最大顶点数
#define INF 32767 // 表示无穷大
typedef struct {
int n; // 顶点数
int edges[MAXV][MAXV]; // 边权
} MatGraph;
void Dispath(MatGraph g, int dist[], int path[], int s[], int v) {
int apath[MAXV], d;
int i, j, k;
for (i = 0; i < g.n; i++) {
if (s[i] == 1 && i != v) {
printf("从顶点 %d 到顶点 %d 的路径长度为:%d\t路径为:", v, 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("%d", apath[d]);
for (j = d-1; j >= 0; j--) {
printf(",%d", apath[j]);
}
printf("\n");
}
}
}
}
void Dijkstra(MatGraph g, int v) {
int dist[MAXV], path[MAXV], s[MAXV];
int i, mindis, j, u;
for (i = 0; i < g.n; i++) {
dist[i] = g.edges[v][i];
s[i] = 0;
if (g.edges[v][i] < INF) {
path[i] = v;
} else {
path[i] = -1;
}
}
s[v] = 1;
for (i = 0; i < g.n-1; i++) {
mindis = INF;
for (j = 0; j < g.n; j++) {
if (s[j] == 0 && dist[j] < mindis) {
u = j;
mindis = dist[j];
}
}
s[u] = 1;
for (j = 0; j < g.n; j++) {
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;
}
}
}
}
printf("s数组值:");
for (i = 0; i < g.n; i++) {
printf("%3d", s[i]);
}
printf("\n");
printf("dist数组值:");
for (i = 0; i < g.n; i++) {
printf("%3d", dist[i]);
}
printf("\n");
printf("path数组值:");
for (i = 0; i < g.n; i++) {
printf("%3d", path[i]);
}
printf("\n");
printf("Dijkstra 算法求解结果:\n");
Dispath(g, dist, path, s, v);
}
int main() {
MatGraph g = {
6,
{
{0, 10, INF, INF, 5, INF},
{INF, 0, 1, INF, 2, INF},
{INF, INF, 0, 4, INF, INF},
{7, INF, 6, 0, INF, INF},
{INF, 3, 9, 2, 0, 4},
{INF, INF, INF, INF, INF, 0}
}
};
Dijkstra(g, 0);
return 0;
}
```
在上述代码中,我们首先定义了 `Dispath` 函数,用于打印从源点到目标顶点的最短路径。然后定义了 `Dijkstra` 函数,用于计算从源点到各顶点的最短路径。在 `Dijkstra` 函数中,我们首先初始化了 `dist` 数组和 `path` 数组,然后进行循环处理,每次选择一个距离最小的顶点,并将其标记为已处理,然后更新与该顶点相连的其他顶点的距离。最后调用 `Dispath` 函数打印结果。
阅读全文