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

Sj中国智造

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

//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]);
                                }
                        }
                }
        }
}