图的应用----最短路径(C语言+&引用)

test.cpp

#define _CRT_SECURE_N0_WARNINGS 1

#pragma warning (disable:4996)

# include <iostream>
# include <stdio.h>
using namespace std;

# define MAX_LENGTH 1024
# define MAX_VERTEX_NUM 20
# define FALSE 0
# define TRUE 1
typedef enum{
    DG, DN, UDG, UDN
} GraphKind;
typedef int VRType;
typedef int InfoType;
typedef int VertexType;
typedef int PathMatrix;
typedef int ShortPathTable;

typedef struct ArcCell
{
    VRType adj;
    InfoType info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix  arcs;
    int vexnum, arcnum;
    GraphKind kind;
}MGraph;

int CreateDN(MGraph &G)   //构建有向网G
{
    int i = 0, j = 0, k, vi, vj, w;
    printf("请输入有向网的顶点数：");
    scanf("%d", &G.vexnum);
    printf("请输入有向网的弧数：");
    scanf("%d", &G.arcnum);

    for (i = 0; i < G.vexnum; ++i)
    for (j = 0; j < G.vexnum; ++j)
    {
        G.arcs[i][j].info = MAX_LENGTH;
    }

    printf("请输入每一条边依附的顶点及权值-->\n");
    for (k = 0; k < G.arcnum; ++k)
    {
        printf("第%d条边的vi:", k + 1);
        scanf("%d", &vi);
        printf("第%d条边的vj:", k + 1);
        scanf("%d", &vj);
        printf("第%d条边的权值:", k + 1);
        scanf("%d", &w);

        //检验顶点和该边权值的合法性
        i = vi;
        j = vj;
        while (i<0 || i>G.vexnum - 1 || j<0 || j>G.vexnum - 1 || w < 0 || w >= MAX_LENGTH)
        {
            printf("输入非法！\n");
            printf("请重新输入-->\n");
            printf("第%d条边的vi:", k + 1);
            scanf("%d", &vi);
            printf("第%d条边的vj:", k + 1);
            scanf("%d", &vj);
            printf("第%d条边的权值:", k + 1);
            scanf("%d", &w);

            i = vi;
            j = vj;
        }

        G.arcs[i][j].info = w;

    }
    return true;
}

void PrintDN(MGraph G)
{
    printf("---------------------------------------\n");
    printf("顶点  ");
    for (int i = 0; i<G.vexnum; i++)
        printf("%5d", i);
    printf("\n");

    for (int i = 0; i<G.vexnum; i++)
    {
        printf("%5d   ", i);
        for (int j = 0; j<G.vexnum; j++)
            printf("%5d", G.arcs[i][j].info);
        printf("\n");
    }
    printf("---------------------------------------\n");
}

void ShortestPath_DIJ(MGraph G, int v0, PathMatrix Path[MAX_VERTEX_NUM][MAX_VERTEX_NUM], ShortPathTable Dist[MAX_VERTEX_NUM])
{

    int i, j, v, w, min, final[MAX_VERTEX_NUM];
    for (v = 0; v<G.vexnum; ++v)
    {
        final[v] = FALSE;
        Dist[v] = G.arcs[v0][v].info;
        for (w = 0; w<G.vexnum; ++w)
            Path[v][w] = FALSE;
        if (Dist[v]<MAX_LENGTH)
        {
            Path[v][v0] = TRUE;
            Path[v][v] = TRUE;
        }
    }

    Dist[v0] = 0;
    final[v0] = TRUE;

    printf("顶点  ");
    for (i = 0; i<G.vexnum; i++)
        printf("%5d", i);
    printf("\n");

    printf("Step %d :", v0 + 1);
    for (i = 0; i<G.vexnum; i++)
        printf("%5d", Dist[i]);
    printf("\n");

    for (i = 1; i<G.vexnum; ++i)
    {
        min = MAX_LENGTH;
        for (w = 0; w<G.vexnum; ++w)
        if (!final[w])
        if (Dist[w]<min)
        {
            v = w;
            min = Dist[w];
        }
        final[v] = TRUE;

        for (w = 0; w < G.vexnum; ++w)
        {
            printf("%d ", final[w]);
        }

        printf("\nStep %d :", i+1);
        for (w = 0; w<G.vexnum; ++w)
        {
            if (!final[w] && (min + G.arcs[v][w].info<Dist[w]))
            {
                Dist[w] = min + G.arcs[v][w].info;
                for (j = 0; j<G.vexnum; j++)
                    Path[w][j] = Path[v][j];
                Path[w][w] = TRUE;
            }
            printf("%5d", Dist[w]);
        }
        printf("\n");
    }

    for (w = 0; w < G.vexnum; ++w)
    {
        printf("%d ", final[w]);
    }

    printf("\n---------------------------------------\n");
}

void main()
{
    MGraph G;
    int v0 = 0;
    PathMatrix Path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    ShortPathTable Dist[MAX_VERTEX_NUM];

    printf("------从某个源点到其余各顶点的最短路径----迪杰斯特拉算法------\n");
    printf("\n");

    if (CreateDN(G))
        printf("\n构建有向网G成功!\n");

    printf("\n有向网G的带权邻接矩阵：\n");

    PrintDN(G);

    ShortestPath_DIJ(G, v0, Path, Dist);
}