NOJ-用弗洛伊德算法求赋权图的两点间的最短路径的长度-西工大数据结构

    一周多没写了，今天上完课回来清两个。题目如下：

    存储结构和以前的都一样，就是换成floyd算法了，其实时间复杂度和dj是一样的，用dj也差不太多。

    （偷一下老师的图。。。）他就是一个起始点一列一列从上到下遍历，中点随起始点的遍历更新终点步数，终点就是起点和中点在矩阵中的交叉点，最后按需输出就可以。

    以下是我的实现：

#include <stdio.h>
#include <stdlib.h>
struct graphList
{
int vexNum;
int graph[120][120];
};
void run();
void createNewGraphList (struct graphList *gList);
void floydAlgorithm(struct graphList *gList);
void putOut(struct graphList *gList);
int main()
{
run ();
return 0;
}
void run()
{
struct graphList gList;
createNewGraphList (&gList);
floydAlgorithm (&gList);
putOut (&gList);
}
void createNewGraphList(struct graphList *gList)
{
int i,j;
scanf ("%d", &(gList -> vexNum));
for (i=0;i < gList->vexNum; i++)
{
for (j = 0; j < gList -> vexNum; j++)
{
scanf ("%d", &(gList -> graph[i][j]));
}
}
}
void floydAlgorithm(struct graphList *gList)
{
int maxVexNum = gList -> vexNum;
int startI, startJ;
int midI, midJ;
int endI, endJ, endStep;
for (startJ = 0; startJ < maxVexNum; startJ++)
{
for (startI = 0; startI < maxVexNum; startI++)
{
if (gList -> graph[startI][startJ] > 0 && gList -> graph[startI][startJ] < 10000)
{
midI = startJ;
for (midJ = 0; midJ < maxVexNum; midJ++)
{
if (gList -> graph[midI][midJ] > 0 && gList -> graph[midI][midJ] < 10000)
{
endI = startI;
endJ = midJ;
endStep = gList -> graph[startI][startJ] + gList -> graph[midI][midJ];
if (endStep < gList -> graph[endI][endJ])
{
gList -> graph[endI][endJ] = endStep;
}
}
}
}
}
}
}

    以下是各函数注释：

void run()
{
struct graphList gList;
createNewGraphList (&gList);//创建图
floydAlgorithm (&gList);//计算路径
putOut (&gList);//按需输出
}

void createNewGraphList(struct graphList *gList)
{
int i,j;
scanf ("%d", &(gList -> vexNum));//结点数
for (i=0;i < gList->vexNum; i++)
{
for (j = 0; j < gList -> vexNum; j++)
{
scanf ("%d", &(gList -> graph[i][j]));//遍历输入权重
}
}
}

void floydAlgorithm(struct graphList *gList)
{
int maxVexNum = gList -> vexNum;
int startI, startJ;
int midI, midJ;
int endI, endJ, endStep;
for (startJ = 0; startJ < maxVexNum; startJ++)//起点按列
{
for (startI = 0; startI < maxVexNum; startI++)//起点按行
{
if (gList -> graph[startI][startJ] > 0 && gList -> graph[startI][startJ] < 10000)//若有权值（有路走）
{
midI = startJ;//中点坐标
for (midJ = 0; midJ < maxVexNum; midJ++)//中点按列
{
if (gList -> graph[midI][midJ] > 0 && gList -> graph[midI][midJ] < 10000)//若有权值（有路走）
{
endI = startI;//终点为交叉点
endJ = midJ;
endStep = gList -> graph[startI][startJ] + gList -> graph[midI][midJ];
if (endStep < gList -> graph[endI][endJ])//若新路步数较少，就更新
{
gList -> graph[endI][endJ] = endStep;
}
}
}
}
}
}
}

void putOut(struct graphList *gList)
{
int n;
int i, j;
scanf ("%d", &n);//需输出的个数
while (n--)
{
scanf ("%d%d", &i, &j);
printf ("%dn", gList -> graph[i][j]);//输出
}
}

最后

以上就是眯眯眼丝袜为你收集整理的NOJ-用弗洛伊德算法求赋权图的两点间的最短路径的长度-西工大数据结构的全部内容，希望文章能够帮你解决NOJ-用弗洛伊德算法求赋权图的两点间的最短路径的长度-西工大数据结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。