基于Dijsktra算法的最短路径求解

数据结构

数据结构笔记

发布日期: 2020-06-09

更新日期: 2020-06-10

文章字数: 853

阅读次数:

本文是记录数据结构习题解析与实验指导的课后实验七——基于Dijsktra算法的最短路径求解。

@[TOC]

1 实验内容

描述
一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。

输入
多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。

输出
每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。

【样例输入】
3 3
A B C
A B 1
B C 1
A C 3
A C

6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
E D 20
E F 60
D F 10
A F

0 0

【样例输出】
2
A B C

60
A E D F

2 基本思路

这个实验属于迪杰斯特拉的模板题，也就是先存储图，然后套迪杰斯特拉的模板就ok了，唯一不同的是他输入的是字母，这样的话，就把它减65，这样方便操作。

3 全部代码

#include<stdio.h>
#define MAXVEX 100
#define INFINITY 65535
typedef int EdgeType;
typedef char VertexType;

typedef struct
{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexs, numEdges;
}MGraph;

void CreateMGraph(MGraph *G)
{
    int row = 0, column = 0, value = 0;
    printf("请输入顶点数和边数\n");
    scanf("%d %d",&G->numVertexs, &G->numEdges);
    if (!G->numVertexs && !G->numEdges)
    {
        return ;
    }
    getchar();
    printf("请输入顶点\n");
    for (int i = 0; i < G->numVertexs; ++i)
    {
        scanf("%c",&G->vexs[i]);
        getchar();
    }
    for (int i = 0; i < G->numVertexs; ++i)
    {
        for (int j = 0; j < G->numVertexs; ++j)
        {
            G->arc[i][j] = INFINITY;
        }
    }
    printf("请输入边\n");
    for (int i = 0; i < G->numEdges; ++i)
    {
        scanf("%c %c %d",&row, &column, &value);
        getchar();
        G->arc[row-65][column-65] = value;
        G->arc[column-65][row-65] = value;
    }
}

void shortestPath_Dijkstra(MGraph *g, int start, int end)
{
    int len = g->numVertexs;
    int visited[len];
    int path[len];
    int pre[len];
    int min, k = 0;
    for (int i = 0; i < len; ++i)
    {
        visited[i] = 0;
        path[i] = g->arc[start][i];
        pre[i] = start;
    }
    visited[start] = 1;
    for (int m = 1; m < len; ++m)
    {
        min = INFINITY;
        for (int i = 0; i < len; ++i)
        {
            if (!visited[i] && min > path[i])
            {
                min = path[i];
                k = i;
            }
        }
        visited[k] = 1;
        for (int j = 0; j < len; ++j)
        {
            if (!visited[j] && min + g->arc[k][j] < path[j])
            {
                path[j] = g->arc[k][j] + min;
                pre[j] = k;
            }
        }
    }
    char temp[len];
    k = len-1;
    printf("%d\n",path[end]);
    while(end != start)
    {
        temp[k--] = g->vexs[end];
        end = pre[end];
    }
    temp[k] = g->vexs[end];
    while (k < len)
    {
        printf("%c ",temp[k++]);
    }
}

void show(MGraph *g)
{
    for (int i = 0; i < g->numVertexs; ++i)
    {
        for (int j = 0; j < g->numVertexs; ++j)
        {
            printf("%7d",g->arc[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    freopen("6.txt","r",stdin);
    char start, end;
    MGraph *g = (MGraph*)malloc(sizeof(MGraph));
    CreateMGraph(g);
    scanf("%c %c", &start, &end);
    shortestPath_Dijkstra(g, start-65, end -65);
    //show(g);
    return 0;
}