程序代码：

#include<stdio.h>
#include<stdlib.h>
#define maxint 32767
typedef struct
{
    char vex[100];
    int a[100][100];
}map;
typedef enum{FALSE,TRUE} boolean;
int d1[100], p1[100];
int d[100][100], p[100][100];
void dijk(map &g, int v1, int n)   //迪杰斯特算法
{
    int d[100], p[100];
    boolean s[100];
    int v, i, w, min;
    for (v = 1; v <= n; v++)    //初始化
    {
        s[v] = FALSE;
        d[v] = g.a[v1][v];
        if (d[v] < maxint)
            p[v] = v1;     //v1是v的前趋
        else
            p[v] = 0;      //v无前趋
    }
    d[v1] = 0; 
    s[v1] = TRUE;
    for (i = 2; i < n; i++)    //n-1个顶点
    {
        min = maxint;
        for (w = 1; w <= n; w++)
            if (!s[w] && d[w] < min)
            {
                v = w;
                min = d[w];
            }
        s[v] = TRUE;
        for (w = 1; w <= n; w++)
            if (!s[w] && (d[v] + g.a[v][w] < d[w]))
            {
                d[w] = d[v] + g.a[v][w];
                p[w] = v;
            }
    }
    printf("路径长度     路径\n");
    for (i = 1; i <= n; i++)
    {
        printf("%5d", d[i]);
        printf("%5d", i);
        v = p[i];
        while (v != 0)
        { 
            printf("<--%d", v);
            v = p[v];
        }
        printf("\n");
    }
}
void floyd(map g, int n)
{
    for (int i = 1; i <= n; i++)         //设置路径长度d初值
        for (int j = 1; j <= n; j++)
        {
            if (g.a[i][j] != maxint)
                p[i][j] = j;
            else
                p[i][j] = 0;
            d[i][j] = g.a[i][j];
        }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (d[i][k] + d[k][j] < d[i][j])
                {
                    d[i][j] = d[i][k] + d[k][j];  //修改长度
                    p[i][j] = p[i][k];
                }
            }
    }
}
void createmap(map &g, int n, int e)
{
    int i, j, k, w;
    for (i = 1; i <= n; i++)
        g.vex[i] = (char)i;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            g.a[i][j] = maxint;
    printf("输入%d条边的i、j、w:\n",e);
    for (k = 1; k <= e; k++)
    {
        scanf_s("%d%d%d", &i,&j,&w);
        g.a[i][j] = w;
    }
    printf("建立完毕\n");
}
void main()
{
    map g;
    int n, e, v, w, k;
    int flag = 1;
    printf("输入图中顶点个数和边数n,e:");
    scanf_s("%d%d", &n, &e);
    createmap(g, n, e);
    while (flag!=0)
    {
        printf("**********求城市最短路径**********\n");
        printf("1、求一个城市到所有城市的最短路径\n");
        printf("2、求任意的两个城市之间的最短路径\n");
        printf("0、退出\n");
        scanf_s("%d", &flag);
        if (flag == 1)
        {
            printf("求单源路径，输入源点v：");
            scanf_s("%d", &v);
            dijk(g, v, n);    //调用迪杰斯特算法
            printf("\n\n");
        }
        else if (flag == 2)
        {
            floyd(g, n);     //调用弗洛伊德算法
            printf("输入源点v和终点w：");
            scanf_s("%d%d", &v, &w);
            k = p[v][w];       //k为起点v的后继算法
            if (k == 0)
                printf("顶点%d到%d无路径！\n", v, w);
            else
            {
                printf("顶点%d到%d的最短路径是:  %d", v, w, v);
                while (k != w)
                {
                    printf("-->%d", k);  //输出后继顶点
                    k = p[k][w];
                }
                printf("-->%d", w);  //终点
                printf("\n路径长度：%d\n", d[v][w]);
                printf("\n\n");
            }
        }
        else
            printf("已选择退出\n");
    }
}