迪杰斯特拉算法之解决最省钱的出游方案

Question

用迪杰斯特拉最短路径算法解决最省钱的出游方案。即给定一个出发地和目的地，给出最省钱的出游方案。各地票价如下：

出发地 目的地 票价
广州 北京 1000
广州 深圳 200
广州 上海 800
深圳 北京 700
深圳 上海 600
深圳 拉萨1000
北京 广州 1000
北京 上海 500
北京 深圳 700
上海 广州 700
上海 北京 500
上海 深圳 700
上海 拉萨1200
拉萨 上海 1100

Answer 1

运行结果（ctrl+z结束输入，vs2022需要连续输入3次才ctrl+z可以）：

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MM 100


//站点信息
typedef struct node
{
    int cost;      //两个站点间的花费
    int vexnode;   //顶点编号
    char name[30]; //站点名称
    struct node* next;
}Arcnode;

typedef struct _graph
{
    Arcnode* point[MM];
    int  vexnum;
} graph;
//队列
typedef struct queue
{
    int father;
    int son;
    struct queue* next;
}queue;

queue* init_queue()
{
    queue* head = (queue*)malloc(sizeof(queue));
    head->next = 0;
    return head;
}
//1为空
int empty(queue* head)
{
    if (head == 0)
        return 1;
    else
        return 0;
}
//入栈
void push(queue* head, int i, int j)   // i:father point   j:son point
{
    queue* tmp = head;
    queue* nn = (queue*)malloc(sizeof(queue));
    nn->father = j;
    nn->next = 0;
    //nn->son = j;
    while (tmp->next)
        tmp = tmp->next;
    tmp->next = nn;

}
//出栈
void pop(queue* head, int* i, int* j)
{
    queue* tmp = head;
    queue* pre = head;
    if (head->next == 0)
    {
        *j = head->father;
        free(head);
        head = 0;
    }
    else
    {
        tmp = head->next;
        while (tmp->next)
        {
            pre = tmp;
            tmp = tmp->next;
        }
        *j = tmp->father;
        free(tmp);
        pre->next = 0;
    }
}

//根据名字查找节点是否存在，如果存在返回节点编号，否则返回-1
int findVertex(graph* g, char* name)
{
    int i;
    for (i = 0; i < g->vexnum; i++)
    {
        if (strcmp(g->point[i]->name, name) == 0)
            return i;
    }
    return -1;
}


//读数据并创建图
void  readAndCreatGraph(graph* g)
{
    Arcnode* tmpnode, * curnode,*head;
    int i = 0, j;
    int cost;
    char name[30] = { 0 }, dst[30] = { 0 };
    g->vexnum = 0;
    while (scanf("%s %s %d",name,dst,&cost)!= EOF)
    {
        //查看节点是否已经存在
        i = findVertex(g, name);
        if (i == -1) //节点不存在
        {
            curnode = (Arcnode*)malloc(sizeof(Arcnode));
            curnode->vexnode = g->vexnum;
            strcpy(curnode->name, name);
            //创建当前节点的链表
            head = (Arcnode*)malloc(sizeof(Arcnode));
            head->vexnode = g->vexnum;
            head->next = 0;
            curnode->next = head; //第一个节点不存储内容
            g->point[g->vexnum] = curnode;
            g->vexnum += 1; //个数加1

            //将目的节点插入链表
            j = findVertex(g, dst);
            curnode = (Arcnode*)malloc(sizeof(Arcnode));
            curnode->cost = cost;
            curnode->next = 0;
            strcpy(curnode->name, dst);
            if (j == -1)
                curnode->vexnode = g->vexnum;
            else
                curnode->vexnode = j;
            //将节点插入
            head->next = curnode;

            //如果目的节点不再图中
            if (j == -1)
            {
                tmpnode = (Arcnode*)malloc(sizeof(Arcnode));
                tmpnode->vexnode = g->vexnum;
                strcpy(tmpnode->name, dst);
                head = (Arcnode*)malloc(sizeof(Arcnode));
                head->vexnode = g->vexnum;
                head->next = 0;
                tmpnode->next = head;
                g->point[g->vexnum] = tmpnode;
                g->vexnum += 1; //节点数+1
            }
            
        }
        else
        {
            //源节点已经存在
            tmpnode = g->point[i]->next; //得到链表头
            curnode = (Arcnode*)malloc(sizeof(Arcnode));
            curnode->cost = cost;
            curnode->next = 0;
            strcpy(curnode->name, dst);
            j = findVertex(g, dst); //看看目的节点是否已经存在
            if (j == -1)
                curnode->vexnode = g->vexnum;
            else
                curnode->vexnode = j;
            while (tmpnode->next)
                tmpnode = tmpnode->next;
            tmpnode->next = curnode;

            //如果目的节点不存在，将该节点插入图中
            if (j == -1)
            {
                tmpnode = (Arcnode*)malloc(sizeof(Arcnode));
                tmpnode->vexnode = g->vexnum;
                strcpy(tmpnode->name, dst);
                head = (Arcnode*)malloc(sizeof(Arcnode));
                head->vexnode = g->vexnum;
                head->next = 0;
                tmpnode->next = head;
                g->point[g->vexnum] = tmpnode;
                g->vexnum += 1;
            }
        }

        

    }

}


//找最短路径
void dijkstra(graph* g)
{
    int inqueue[MM] = { 0 };  //是否已经入栈
    int id, start_s;
    Arcnode* ns = 0;
    queue* last = 0;  //队列的最后一个元素
    int una, unb, xx = 0, yy = 0;
    queue* head = 0;


    int pathMin[MM] = { 0 };                //最短路径
    int pathTmp[MM] = { 0 };                //临时路径
    int minDistance = -1, tmpdis = 0;       //最短路径距离
    int lengpath = 0, minpathlen = 0;       //最短路径点个数
    queue* qMin = 0;
    int kktt = 0, vv = 0;

    int start, end; //起点和终点
    char str_start[30], str_end[30];
    int flags[MM][MM];
    //system("cls");


    //显示地图信息
    //showBaseInfo(g);

    printf("请输入起点和终点:");
    scanf("%s %s", str_start , str_end);
    start = findVertex(g,str_start);
    end = findVertex(g,str_end);

    //初始化邻接矩阵
    for (xx = 0; xx < MM; xx++)
    {
        for (yy = 0; yy < MM; yy++)
            flags[xx][yy] = -1;
    }
    for (xx = 0; xx < g->vexnum; xx++)
    {
        ns = g->point[xx]->next;
        while (ns)
        {
            flags[xx][ns->vexnode] = 0;
            ns = ns->next;
        }
    }

    //起点入栈
    head = init_queue();
    head->father = start;
    inqueue[start] = 1;    //起点已入栈

    while (!empty(head))
    {
        //获取队列中的最后一个元素
        last = head;
        while (last->next)
            last = last->next;
        start_s = last->father;

        //获取队列中最后一个元素的一个可到达的站
        id = -1;
        for (xx = 0; xx < g->vexnum; xx++)
        {
            if (flags[start_s][xx] == 0)
            {
                flags[start_s][xx] = 1;
                id = xx;
                break;
            }
        }

        //如果未找到
        if (id == -1)
        {
            pop(head, &una, &unb); //栈弹出一个元素
            if (unb == start) head = 0;
            //查找unb所有相邻节点，并将其状态设为未访问

            for (xx = 0; xx < MM; xx++)
            {
                if (flags[unb][xx] == 1) flags[unb][xx] = 0;
            }

            inqueue[start_s] = 0; //该顶点标记为未入栈
            continue;             //取栈顶的相邻节点
        }
        if (inqueue[id])  //若已经在栈中，取下一个顶点
        {
            continue;
        }


        push(head, 0, id);            //将该顶点入栈
        inqueue[id] = 1;            //记为已入栈
        if (id == end)              //如果栈顶已经为所求，将此路径记录
        {
            //-----------------计算路径的长度-----------------------------
            qMin = head;
            lengpath = 0;
            while (qMin)
            {
                pathTmp[lengpath] = qMin->father;
                lengpath++;
                qMin = qMin->next;
            }
            tmpdis = 0;
            for (kktt = 0; kktt < lengpath - 1; kktt++)
            {
                vv = pathTmp[kktt];
                ns = g->point[vv]->next;
                while (ns)
                {
                    if (ns->vexnode == pathTmp[kktt + 1])
                    {
                        tmpdis += ns->cost;
                        break;
                    }
                    else
                        ns = ns->next;
                }
            }

            //显示所有路径
            printf("花费=%d : ", tmpdis);
            for ( xx = 0; xx < lengpath; xx++)//int
            {
                if (xx < lengpath - 1)
                    printf("%s --> ", g->point[pathTmp[xx]]->name);
                else
                    printf("%s\n",g->point[pathTmp[xx]]->name );
            }
            //找最短路径
            if (minDistance == -1 || minDistance > tmpdis)
            {
                minDistance = tmpdis;
                minpathlen = lengpath;
                for ( xx = 0; xx < lengpath; xx++)//int
                    pathMin[xx] = pathTmp[xx];
            }

            //--------------------------------------------------------------
            pop(head, &una, &unb); //将其弹出，继续探索
            if (unb == start) head = 0;
            inqueue[id] = 0;     //清空入栈的标志位
        }
    } //while end

    //打印最短路径
    if (minDistance == -1)
    {
        printf("无可用路径\n");
        return;
    }
    printf("\n最小花费:%d:", minDistance);
    for (kktt = 0; kktt < minpathlen; kktt++)
    {
        if (kktt < minpathlen - 1)
            printf("%s --> ", g->point[pathMin[kktt]]->name);
        else
            printf("%s\n", g->point[pathMin[kktt]]->name);
    }
}


int main()
{
    graph g;
    g.vexnum = 0;
    readAndCreatGraph(&g);
    dijkstra(&g);
    return 0;
}