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); }修改完善并给出代码
时间: 2024-03-16 07:41:41 浏览: 22
以下是修改完善后的 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` 函数打印结果。