图的两个最短路径算法（邻接表实现）

Sj中国智造 · 发表于 2018-11-8 15:30:51

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

写了两个最短路径算法的邻接表版，但并没测试过，所以可能有错误，若发现有错误，可以在下面留言。

//AdjList.h
#pragma once
//邻接表的储存结构
#define INFINITY 0
#define MAX_VERTEX_NUM 1025
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int weight;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
int kind;
}ALGraph;
//ShortestPath.h
#pragma once
#include "AdjList.h"
//最短路径——迪杰斯特拉算法和弗洛伊德算法(邻接表版)
//这里所有数组中的0下标都未使用
typedef int PathArc[MAX_VERTEX_NUM]; //用来储存最短路径前驱下标的数组
typedef int ShortPathTable[MAX_VERTEX_NUM]; //用来储存到各点的权值和
//函数功能：寻找v0到v1顶点的直连路径长度
//函数参数：图的邻接表G，起始顶点v0，到达顶点v1
//函数返回值：直连路径的长度，若没有直连长度，返回INFINITY
int PathDistance(ALGraph G, int v0, int v1);
//函数功能：自定义比较路径长度
//函数参数：要比较的路径长度distance1和distance2
//函数返回值：-1代表前一个参数小于后一个参数，0代表两者相等，1代表前一个参数大于后一个参数
int PathCompare(int distance1, int distance2);
//函数功能：自定义路径相加
//函数参数：要相加的两个路径长度distance1和distance2
//函数返回值：两个路径长度相加的结果
int PathAdd(int distance1, int distance2);
//函数功能：寻找一个顶点到其余各点的最短路径(迪杰斯特拉算法)
//函数参数：图的邻接表G，起始顶点v0，最短路径前驱下标的数组P，到各点的长度S
//函数返回值：void
void ShortestPath_DIJ(ALGraph G, int v0, PathArc P, ShortPathTable S);
//函数功能：寻找一个顶点到其余各点的最短路径（弗洛伊德算法）
//函数参数：图的邻接表G，储存各点到其他点的最短路径的前驱顶点P[]，储存各点到其他点的最短路径的长度S[]
//函数返回值：void
void ShortestPath_FLOYD(ALGraph G, PathArc p[], ShortPathTable S[]);
//ShortestPath.c
#include <stdio.h>
#include <stdlib.h>
#include "ShortestPath.h"
//最短路径——迪杰斯特拉算法和弗洛伊德算法(邻接表版)
//实现部分
//函数功能：寻找v0到v1顶点的直连路径长度
//函数参数：图的邻接表G，起始顶点v0，到达顶点v1
//函数返回值：直连路径的长度，若没有直连长度，返回INFINITY
int PathDistance(ALGraph G, int v0, int v1)
{
ArcNode *arcNode;
arcNode = G.vertices[v0].firstarc;
while (arcNode != NULL && arcNode->adjvex != v1)
{//寻找直连路径
arcNode = arcNode->nextarc;
}
if (arcNode != NULL)
{//找到直连路径时，返回直连路径长
return arcNode->weight;
}
else
{//未找到直连长度时，返回INFINITY
return INFINITY;
}
}
//函数功能：自定义比较路径长度
//函数参数：要比较的路径长度distance1和distance2
//函数返回值：-1代表前一个参数小于后一个参数，0代表两者相等，1代表前一个参数大于后一个参数
int PathCompare(int distance1, int distance2)
{
if (distance1 == INFINITY)
{
if (distance2 == INFINITY)
{
return 0;
}
else
{
return 1;
}
}
else if (distance2 == INFINITY)
{
return -1;
}
else
{
distance1 >= distance2 ? (distance1 == distance2 ? 0 : 1) : -1;
}
}
//函数功能：自定义路径相加
//函数参数：要相加的两个路径长度distance1和distance2
//函数返回值：两个路径长度相加的结果
int PathAdd(int distance1, int distance2)
{
if (distance1 == INFINITY || distance2 == INFINITY)
{
return INFINITY;
}
else
{
return distance1 + distance2;
}
}
//函数功能：寻找一个点到其余各点的最短路径(迪杰斯特拉算法)
//函数参数：图的邻接表G，起始顶点v0，最短路径前驱下标的数组P，到各点的长度S
//函数返回值：void
void ShortestPath_DIJ(ALGraph G, int v0, PathArc P, ShortPathTable S)
{
int w,v;
int min;
int final[MAX_VERTEX_NUM]; //记录是否找到某一顶点的最短路径
for (v = 1; v <= G.vexnum; v++)
{//初始化
final[v] = 0;
P[v] = v0;
S[v] = PathDistance(G, v0, v);
}
final[v0] = 1; S[v0] = 0; //顶点v0到自身的路径为0
for (int i = 2; i <= G.vexnum; i++)
{//找其余vexnum-1个顶点的最短路径所以需要有vexnum-1重循环
min = INFINITY;
for (w = 1; w <= G.vexnum; w++)
{//寻找此时v0到哪个顶点的路径最短
if (!final[w] && PathCompare(S[w], min) < 0)
{//找到更短路径，更新路径最小值
v = w;
min = S[w];
}
}
if (min == INFINITY) break; //若在一次查找中，找不到最短路径，则整个循环结束
final[v] = 1;
for (w = 1; w <= G.vexnum; w++)
{//通过此次找到的最短路径的顶点来更新到其他顶点的路径
if (!final[w] && PathCompare(PathAdd(min, PathDistance(G, v, w)), S[w]) < 0)
{//说明找到了更短的路径，更新到该顶点的前驱结点和最短路径
S[w] = PathAdd(min, PathDistance(G, v, w));
P[w] = v;
}
}
}
}
//函数功能：寻找一个顶点到其余各点的最短路径（弗洛伊德算法）
//函数参数：图的邻接表G，储存各点到其他点的最短路径的前驱顶点P[]，储存各点到其他点的最短路径的长度S[]
//函数返回值：void
void ShortestPath_FLOYD(ALGraph G, PathArc P[], ShortPathTable S[])
{
int k, w, v;
for (v = 1; v <= G.vexnum; v++)
{
for (w = 1; w <= G.vexnum; w++)
{//初始化
P[v][w] = v; //假设w到v的直连路径最短
S[v][w] = PathDistance(G, v, w);
}
}
for (k = 1; k <= G.vexnum; k++)
{
for (v = 1; v <= G.vexnum; v++)
{
for (w = 1; w <= G.vexnum; w++)
{
if (PathCompare(S[v][w], PathAdd(S[v][k], S[k][w])) > 0)
{//如果经过下标为k的顶点的路径更短，更新最短路径
P[v][w] = S[k][w];
S[v][w] = PathAdd(S[v][k], S[k][w]);
}
}
}
}
}

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 图的两个最短路径算法（邻接表实现）

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块