数据结构与算法-图的最短路径

作者: 恍然如梦_b700 | 来源:发表于2020-05-15 19:07 被阅读0次

数据结构与算法--最短路径之Floyd算法
《算法》笔记 12 - 最短路径
图的应用-最短路径求解
数据结构与算法--最短路径之Bellman算法、SPFA算法
头条-手撕代码
python 狄克斯特拉算法
数据结构与算法-图的最短路径算法
数据结构与算法学习 (14)最短路径求解
数据结构与算法-最短路径问题
最短路径算法（D算法）

一、Dijkstra算法

2322.002.jpeg

最短路径: V0 — V1 — V2 — V4 — V3 —V6 —V7 — V8
最短路径权值和: 1 + 3 + 1 + 2 +3 + 2 + 4 = 16

image.png

了解几个关键数组

image.png

1. final数组作⽤: 表示V0 到某个顶点 Vw 是否已经

求得了最短路径的标记. 如果V0 到 Vw 已经有结
果,则final[w] = 1;

2. D数组作⽤: 表示V0 到某个顶点 Vw 的路径权值;

3.p数组作⽤: 当前顶点的前驱顶点的下标;

#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/*用于存储最短路径当前节点的前驱节点下标的数组，*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];

/*10.1 创建邻近矩阵*/
void CreateMGraph(MGraph *G)
{
    int i, j;
    
    G->numEdges=16;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)
    {
        G->vexs[i]=i;
    }
    
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    
    G->arc[7][8]=4;
    
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/*10.2 求得网图中2点间最短路径
 Dijkstra 算法
 G: 网图;
 v0: V0开始的顶点;
 p[v]: 前驱顶点下标;
 D[v]: 表示从V0到V的最短路径长度和;
 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
    int v,w,k,min;
    k = 0;
    /*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
    int final[MAXVEX];
    //1.初始化
    for (v = 0; v < G.numVertexes; v++) {
        //全部顶点初始化为0
        final[v] = 0;
        //将与V0点有连线的顶点最短路径值存到数组D中;
        (*D)[v] = G.arc[v0][v];
        //初始化路径数组p = 0;
        (*P)[v] = 0;
    }
    //V0到V0的路径为0
    (*D)[v0] = 0;
    //V0到V0 是没有路径的.
    final[v0] = 1;
    //v0到V0是没有路径的
    (*P)[v0] = -1;
    
    //2. 开始主循环,每次求得V0到某个顶点的最短路径
    for (v = 1; v < G.numVertexes; v++) {
        
        //当前所知距离V0顶点最近的距离，找到最小权值
        min = INFINITYC;
        /*3.寻找离V0最近的顶点*/
        for (w = 0; w < G.numVertexes; w++) {
            //当前顶点未找到过最短路径
            if (!final[w] && (*D)[w] < min) {
                min = (*D)[w];
                k = w;//w顶点距离V0顶点更近
            }
        }
        
        final[k] = 1;//下次循环就会找不为1的顶点
        /*4.把刚刚找到v0到k最短路径的基础上,对于k 与 其他顶点的边进行计算,得到v0与它们的当前最短距离;*/
        for(w=0; w<G.numVertexes; w++)
        {
             //如果经过v顶点的路径比现在这条路径长度短,则更新
            if (!final[w] && min + G.arc[k][w] < G.arc[v0][w]) {
                //找到更短路径, 则修改D[W],P[W]
                //修改当前路径的长度
                (*D)[w] = min + G.arc[k][w];
                (*P)[w] = k;
            }
            
        }
        
    }

}

int main(int argc, const char * argv[]) {
    printf("最短路径-Dijkstra算法\n");
    int i,j,v0;
    MGraph G;
    Patharc P;
    ShortPathTable D;
    v0=0;
    
    CreateMGraph(&G);
    
    ShortestPath_Dijkstra(G, v0, &P, &D);
    for (i = 0; i<G.numVertexes; i++) {
        printf("%d ",P[i]);
    }
    printf("最短路径路线:\n");
    for(i=1;i<G.numVertexes;++i)
    {
        printf("v%d -> v%d : ",v0,i);
        j=i;
        while(P[j]!=-1)
        {
            printf("%d ",P[j]);
            j=P[j];
        }
        printf("\n");
    }
    
    printf("\n最短路径权值和\n");
    for(i=1;i<G.numVertexes;++i)
        printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);
    
    printf("\n");
    return 0;
}

二、Floyd算法

算法原理

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。定义一个矩阵P用来记录所插入点的信息，P[i][j]表示从Vi到Vj需要经过的点，初始化P[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则P[i][j]=k。在G中包含有两点之间最短道路的信息，而在P中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据P，假如P(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果P(5,3)=3，说明V5与V3直接相连，如果P(3,1)=1，说明V3与V1直接相连。

所有顶点到所有顶点之间的最短路径权值都已经计算完成; 那么我们如何从Floyd 算法中
找到具体的最短路径了? 例如怎么求得V0~V8的最短路径以及路径总和?
以V0 ~ V8 为例, 从D数组中, P[0][8] = 1, 得到要经过顶点V1, 然后将1取代0得到P[1][8] = 2; 说明
需要经过V2,则将2取代1得到P[2][8] = 4, 则表示需要经过V4,则将4取代2得到P[4][8] = 3, 说明…… 以此类推,推导最终的最短路径为 V0_V1V2_V4V3_V6V7~V8;

#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

/* 11.1 构成邻近矩阵 */
void CreateMGraph(MGraph *G)
{
    int i, j;
    
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=16;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        G->vexs[i]=i;
    }
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    
    G->arc[7][8]=4;
    
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/* 11. 2
 Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
 Patharc 和 ShortPathTable 都是二维数组;
 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
    int v,w,k;
    
    /* 1. 初始化D与P 矩阵*/
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            /* D[v][w]值即为对应点间的权值 */
            (*D)[v][w]=G.arc[v][w];
             /* 初始化P P[v][w] = w*/
            (*P)[v][w]=w;
        }
    }
    
    //2.K表示经过的中转顶点
    for(k=0; k<G.numVertexes; ++k)
    {
        for(v=0; v<G.numVertexes; ++v)
        {
            for(w=0; w<G.numVertexes; ++w)
            {
                /*如果经过下标为k顶点路径比原两点间路径更短 */
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {
                    /* 将当前两点间权值设为更小的一个 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
                    /* 路径设置为经过下标为k的顶点 */
                    (*P)[v][w]=(*P)[v][k];
                }
            }
        }
    }
}

int main(void)
{
    printf("Hello,最短路径弗洛伊德Floyd算法");
    int v,w,k;
    MGraph G;
    
    Patharc P;
    ShortPathTable D; /* 求某点到其余各点的最短路径 */
    
    CreateMGraph(&G);
    
    ShortestPath_Floyd(G,&P,&D);
    
    //打印所有可能的顶点之间的最短路径以及路线值
    printf("各顶点间最短路径如下:\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=v+1; w<G.numVertexes; w++)
        {
            printf("v%d-v%d weight: %d ",v,w,D[v][w]);
            //获得第一个路径顶点下标
            k=P[v][w];
            //打印源点
            printf(" path: %d",v);
            //如果路径顶点下标不是终点
            while(k!=w)
            {
                //打印路径顶点
                printf(" -> %d",k);
                //获得下一个路径顶点下标
                k=P[k][w];
            }
            //打印终点
            printf(" -> %d\n",w);
        }
        printf("\n");
    }
    
    //打印最终变换后的最短路径D数组
    printf("最短路径D数组\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d\t",D[v][w]);
        }
        printf("\n");
    }
    //打印最终变换后的最短路径P数组
    printf("最短路径P数组\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d ",P[v][w]);
        }
        printf("\n");
    }
    
    return 0;
}

数据结构与算法--最短路径之Floyd算法
数据结构与算法--最短路径之Floyd算法我们知道Dijkstra算法只能解决单源最短路径问题，且要求边上的权重...
《算法》笔记 12 - 最短路径
加权有向图数据结构加权有向边加权有向图最短路径边的松弛 Dijkstra算法地图或者导航系统是最短路径的典型...
图的应用-最短路径求解
图的最短路径图的最短路径是一个起点到一个终点之间最短的路径。用于解决最短路径问题的算法被称做“最短路径算...
数据结构与算法--最短路径之Bellman算法、SPFA算法
数据结构与算法--最短路径之Bellman算法、SPFA算法除了Floyd算法，另外一个使用广泛且可以处理负权边...
头条-手撕代码
[toc] 图算法以及最短路径算法树算法手写LRU 排序算法链表算法
python 狄克斯特拉算法
前言狄克斯特拉算法是解决加权图求最短路径的算法，广度优先算法可以求非加权图的最短路径，但是如果图的边权重不一样，...
数据结构与算法-图的最短路径算法
0. 数据结构注意:以下算法提到的v0可以是任意顶点，实现的时候可能需要调整一下代码，这里以v0顶点为索引0生成...
数据结构与算法学习 (14)最短路径求解
最短路径问题是图研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形...
数据结构与算法-最短路径问题
最短路径问题是图研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形...
最短路径算法（D算法）
解决最短路径算法的D算法，是一个解决从点到点之间最短路径的问题，看下面这张图：