数据结构课程设计题

发布网友发布时间：2022-04-25 14:51

共1个回答

热心网友时间：2023-10-10 01:22

最短路径问题
#include "datastru.h"
#include <stdio.h>
#include <malloc.h>
#define MAX 10000

MGRAPH create_mgraph(){
/*建立有向图的邻接矩阵结构*/
int i, j, k, h;
MGRAPH mg;

mg.kind = 3;
printf("\n\n输入顶点数和边数(用逗号隔开) : ");
scanf("%d,%d", &i,&j);
mg.vexnum = i; /*存放顶点数在mg.vexnum中 */
mg.arcnum = j; /*存放边点数在mg.arcnum中*/
fflush(stdin);
for(i = 0; i < mg.vexnum; i++)
{ printf("输入顶点 %d 的值 : ",i + 1); /*输入顶点的值*/
scanf("%d", &mg.vexs[i]);
fflush(stdin);}
for(i = 0; i < mg.vexnum; i++) /*邻接矩阵初始化*/
for(j = 0; j < mg.vexnum; j++)
mg.arcs[i][j] = MAX;
for(k = 1; k <= mg.arcnum; k++)
{ printf("输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ",k);
scanf("%d,%d",&i,&j); /*输入弧的起始顶点和终止顶点*/
fflush(stdin);
while(i < 1 || i > mg.vexnum || j < 1 || j > mg.vexnum)
{ printf("输入错，重新输入: ");
scanf("%d,%d", &i, &j);}
printf("输入此边权值 : "); /*输入弧上之权值*/
scanf("%d", &h);
mg.arcs[i - 1][j - 1] = h;}
return mg;
}

main()
{
MGRAPH mg;
int cost[MAXLEN][MAXLEN];
int path[MAXLEN], s[MAXLEN];
int dist[MAXLEN];
int i, j, n, v0, min, u;

printf("\n求有向图单源点最短路径\n");
mg = create_mgraph(); /*建立有向图的邻接矩阵结构*/
printf("\n\n起始顶点为 : "); /*有向图中顶点的编号从1编起*/
scanf("%d", &v0);
v0 --;
n = mg.vexnum;
for(i = 0; i < n; i++) /*cost矩阵初始化*/
{for(j = 0; j < n; j++)
cost[i][j] = mg.arcs[i][j];
cost[i][i] = 0;}
for(i = 0; i < n; i++)
{dist[i] = cost[v0][i]; /*dist数组初始化*/
if(dist[i] < MAX && dist[i] > 0) /*path数组初始化*/
path[i] = v0;}
for(i = 0; i < n; i++) /*s数组初始化*/
s[i] = 0;
s[v0] = 1;
for(i = 0; i < n; i++) /*按最短路径递增算法计算*/
{ min = MAX ;
u = v0;
for(j = 0; j < n; j++)
if(s[j] == 0 && dist[j] < min)
{min = dist[j];
u = j;}
s[u] = 1; /*u顶点是求得最短路径的顶点编号*/
for(j = 0; j < n; j++)
if(s[j] == 0 && dist[u] + cost[u][j] < dist[j])/*调整dist*/
{dist[j] = dist[u] + cost[u][j];
path[j] = u;} /*path记录了路径经过的顶点*/
}
for(i = 0; i < n; i++) /*打印结果*/
if(s[i] == 1)
{u = i;
while(u != v0)
{printf("%d <- " , u + 1);
u = path[u];}
printf("%d ", u + 1);
printf(" d = %d\n", dist[i]); /*有路径*/
}
else
printf("%d <- %d d= MAX\n ", i + 1, v0 + 1);/*无路径*/
printf("\n\n");
}