精华内容
下载资源
问答
  • 2018-11-03 18:40:21

    目的:掌握栈在求解迷宫问题中的应用。

    内容:编写一个程序,输出迷宫的所有路径,并求第一条最短路径长度及最短路径。

    代码如下:

    #include <iostream>
    #include <cstdio>
    #include <stack>
    #include <cstdlib>
    using namespace std;
    #define inf 0x3f3f3f
    const int MaxSize=1000;
    int M=4,N=4;
    int mg[6][6]={{1,1,1,1,1,1},{1,0,0,0,1,1},
                      {1,0,1,0,0,1},{1,0,0,0,1,1},
                      {1,1,0,0,0,1},{1,1,1,1,1,1}};
    int vis[6][6];
    typedef struct
    {
        int i;//当前方块的行号
        int j;//当前方的列号
        int di;
    }Box;
    typedef struct
    {
        Box data[MaxSize];
        int top;//栈顶指针
    }SqStack;//顺序栈类型
    void InitStack(SqStack *&s)//初始化栈
    {
        s=(SqStack *)malloc(sizeof(SqStack));
        s->top=-1;
    }
    bool Push(SqStack *&s,Box e)//进栈
    {
        if(s->top==MaxSize-1)
            return false;
        s->top++;
        s->data[s->top]=e;
    }
    bool StackEmpty(SqStack *s)//判断栈是否为空
    {
        return (s->top==-1);
    }
    bool Pop(SqStack *&s,Box &e)//出栈
    {
        if(s->top==-1)
            return false;
        e=s->data[s->top];
        s->top--;
        return true;
    }
    bool GetTop(SqStack *s,Box &e)//取出栈顶元素
    {
        if(s->top==-1)
            return false;
        e=s->data[s->top];
        return true;
    }
    bool mgpath(int xi,int yi,int xe,int ye)
    {
        int minn=inf,minum;
        int cont=1;
        int f=0;
        int i,j,di,i1,j1,k;
        bool _find=false;
        SqStack *st;//定义栈st
        InitStack(st);//初始化栈st
        Box e1,e;
        e1.i=xi;
        e1.j=yi;
        e1.di=-1;
        Push(st,e1);//方块e进栈
        vis[xi][yi]=-1;//将入口的迷宫值置为-1,避免重复走到该方块
        while(!StackEmpty(st))//栈不为空时循环
        {
            GetTop(st,e);
            //cout<<e.i<<" "<<e.j<<" "<<e.di<<endl;
            i=e.i;
            j=e.j;
            di=e.di;
            if(i==xe&&j==ye)//找到了出口,输出该路径
            {
                f=1;
                if(st->top<minn)
                {
                    minn=st->top;
                    minum=cont;
                }
                printf("迷宫路径%d为:\n",cont++);
                for(k=0;k<=st->top;k++)
                    printf("(%d,%d)\t",st->data[k].i,st->data[k].j);
                printf("\n");
            }
            _find=false;
            while(di<4&&!_find)
            {
                di++;
                switch(di)
                {
                    case 0:i1=i-1;j1=j;break;
                    case 1:i1=i;j1=j+1;break;
                    case 2:i1=i+1;j1=j;break;
                    case 3:i1=i;j1=j-1;break;
                }
                if(vis[i1][j1]==0&&mg[i1][j1]==0) _find=true;
            }
            if(_find)
            {
                st->data[st->top].di=di;
                e.i=i1;
                e.j=j1;
                e.di=-1;
                Push(st,e);
                vis[i1][j1]=-1;
            }
            else
            {
                Pop(st,e);
                vis[e.i][e.j]=0;
            }
        }
        if(f==1)
        {
            printf("最短路径为路径%d\n",minum);
            printf("最短路径长度为%d\n",minn);
            return true;
        }
        return false;
    }
    int main()
    {
        if(!mgpath(1,1,4,4))
            printf("该迷宫问题没有解!\n");
        return 0;
    }

    运行结果:

    更多相关内容
  • AE+VC#2015 最短路径的源代码,包括测试shp数据,以及数据处理说明和代码使用说明
  • 内包含QT程序运行出来是一个60*60的迷宫,算法包括迷宫的自动生成,利用深度优先搜索、广度优先搜索两种方法遍历最短路径,并能在界面上动态显示。
  • 以下程序在DEV C++中调试运行通过。 #include <stdio> #define INFINITY 65535 typedef int VertexType; //顶点是字符型 typedef int EdgeType; //边是整型 typedef struct //图的邻接矩阵存储结构 { Vertex...
  • 资源名:dijkstra算法_最短路径_MATLAB程序_有效搜索最短路径 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合...
  • 地图最短路径代码

    2019-03-09 18:45:49
    有一张地图,找出任意两点之间的最短路径
  • 主要介绍了Python使用Dijkstra算法实现求解图中最短路径距离问题,简单描述了Dijkstra算法的原理并结合具体实例形式分析了Python使用Dijkstra算法实现求解图中最短路径距离的相关步骤与操作技巧,需要的朋友可以参考下
  • 并行最短路径算法Dijkstra。 为实现并行最短路径计算,我们必须要解决如下问题: (1)数据获取:利用随机函数生成大约2000个节点及其节点之间的距离。本程序使用邻接矩阵来存储带权有向图的信息。矩阵大小2000*2000...
  • DQN找最短路径算法,MATLAB实现,含界面,可运行
  • 使用Python和NetworkX查找通过3D迷宫的最短路径 对于该项目,我们创建了一个文件:maze.py,用于运行迷宫问题程序。 对于此程序,我们将使用控制台输入,因此在第105至107行之间的maze.py文件中,我提供了一种打开和...
  • 文件中详细介绍了最短路径算法实现方案,在VC环境下调试运行可行。
  • 实验名称: 单源最短路径问题 实验地点: 实验目的: 1、 理解分支限界法的剪枝搜索策略; 2、 掌握分支限界法的算法柜架; 3、 掌握分支限界法的算法步骤; 4、 通过应用范例...

    实验名称: 单源最短路径问题

    实验地点:

    实验目的:

    1、  理解分支限界法的剪枝搜索策略;

    2、  掌握分支限界法的算法柜架;

    3、  掌握分支限界法的算法步骤;

    4、  通过应用范例学习动态规划算法的设计技巧与策略;

     

    实验原理

    1. 基本思想

    分支是使用广度优先策略,依次生成扩展结点的所有分支。

    限界是在结点扩展过程中,计算结点的上界,搜索的同时剪掉某些分支。

    分支限界法就是把问题的可行解展开,再由各个分支寻找最佳解。

    与回溯法类似,分支限界法也是在解空间中搜索得到解;

    不同的是,分支限界法会生成所有扩展结点,并舍弃不可能通向最优解的结点,然后根据广度优先/最小耗费优先,从活结点中选择一个作为扩展结点,使搜索向解空间上有最优解的分支推进。

    2. 搜索策略

    分支限界法首先生成当前扩展结点的所有分支,然后再从所有活结点中选择一个作为扩展结点。每一个活结点都要计算限界,根据限界情况判断是否剪枝,或选择最有利的结点。

    实验内容:

    1、使用分支限界法解决单源最短路径问题。

    2、通过上机实验进行算法实现。

    3、保存和打印出程序的运行结果,并结合程序进行分析,上交实验报告。

    源程序:

    方法一:

    //单源最短路径
    
    class Graph{	//带权有向图
    private:
        int n;			//顶点个数
        int **c;		//邻接矩阵
        int *dist;		//记录路径
    public:
        void shortestPaths(int);
        Graph();         //根据情况构造图
    };
    
    class MinHeapNode{		//最小堆的结点
        friend Graph;
    private:
        int i;				//结点对应的顶点编号
        int length;			//结点记录的最短路径
    public:
        int getI(){ return i; }
        void setI(int i){ this->i = i; }
        int getLength(){ return length; }
        void setLength(int length){ this->length = length; }
    };
    
    class MinHeap{		//最小堆(虽然叫堆,但其实并不是用堆实现的)
        friend Graph;
    private:
        int length;			//最小堆的长度,等同于顶点个数
        MinHeapNode *nodes;		//结点数组
    public:
        MinHeap(int n)
        {
            this->length = n;
            nodes = new MinHeapNode[n];
        }
        void deleteMin(MinHeapNode&);	//令当前节点出队列,并给出下一个扩展结点
        void insertNode(MinHeapNode N)		//结点入队列,将原结点的内容替换即可
        {
            nodes[N.getI()].setI(N.getI());
            nodes[N.getI()].setLength(N.getLength());
        }
        bool outOfBounds()		//检查队列为空
        {
            for(int i = 0;i < length;i++)
                if(nodes[i].getI() != -1)
                    return false;
            return true;
        }
    };
    
    void MinHeap::deleteMin(MinHeapNode &E)
    {
        int j = E.getI();
        nodes[j].setI(-1);
        nodes[j].setLength(-1);		//标记为出队列
        int tmp = INT_MAX;
        for(int i = 0;i < length;i++){		//给出路径最短的结点作为扩展结点
            if(nodes[i].getI() != -1 && nodes[i].getLength() < tmp){
                E.setI(i);
                E.setLength(nodes[i].getLength());
                tmp = nodes[i].getLength();
            }
        }
    }
    
    void Graph::shortestPaths(int start)
    {
        MinHeap heap = MinHeap(n);	
        MinHeapNode E = MinHeapNode();		//别问,一开始还加了new,太久不写C++了
        E.i = start;	
        E.length = 0;
        dist[start] = 0;	//初始为源点V,对应编号start
        while(true){
            for(int j = 0;j < n;j++){	//检查所有邻接顶点
                if(c[E.i][j] != 0){		//是否邻接
                    if(E.length + c[E.i][j] < dist[j]){		//是否满足限界,当前路径小于记录的最短路径
                        dist[j] = E.length + c[E.i][j];		//更新
                        if(/*填入判断表达式*/){          //没有邻接顶点的点不入队,按情况调整,没有也可以,但会造成无效开销
                            MinHeapNode N = MinHeapNode();	//创建一个新的结点,并令其入队列
                            N.i = j;
                            N.length = dist[j];
                            heap.insertNode(N);
                        }
                    }
                }
            }
            if(heap.outOfBounds())	//队列为空,结束
                break;
            heap.deleteMin(E);	//该结点已经生成全部分支,出队列并取得下一扩展结点
        }
    }
    

    方法二:

    #include <iostream>
    #include<queue>
    using namespace std;
     
    typedef struct ArcCell{
        int adj;//保存权值
        int info;//存储最短路径长度
    }ArcCell,AdjMaxtrix[100][100];
     
    typedef struct{
        int data;
        int length;
    }VerType;
     
    typedef struct{
        VerType vexs[100];//顶点向量
        AdjMaxtrix arcs;
        int vexnum;//顶点数
        int arcnum;//弧数
    }Graph;
     
    Graph G;
    queue<int> q;
     
    void CreateGraph()
    {
        int m,n,t;
        printf("输入顶点数和弧数:");
        scanf("%d%d",&G.vexnum,&G.arcnum);
        printf("输入顶点:");
        for(int i=1;i<=G.vexnum;i++)
        {
            scanf("%d",&G.vexs[i].data);
            G.vexs[i].length=10000;
        }
     
        for(int i=1;i<=G.vexnum;i++)
            for(int j=1;j<=G.vexnum;j++)
            {
                G.arcs[i][j].adj=0;
            }
     
        printf("输入弧及权重:\n");
        for(int i=1;i<=G.arcnum;i++)
            {
                scanf("%d%d%d",&m,&n,&t);
                G.arcs[m][n].adj=1;
                G.arcs[m][n].info=t;
            }
     
    }
     
    int NextAdj(int v,int w)
    {
        for(int i=w+1;i<=G.vexnum;i++)
            if(G.arcs[v][i].adj)
                return i;
        return 0;//not found;
    }
     
    void ShortestPaths(int v)
    {
        int k=0;//从首个节点开始访问
        int t;
        G.vexs[v].length=0;
        q.push(G.vexs[v].data);
        while(!q.empty())
        {
            t=q.front();
            k=NextAdj(t,k);
            while(k!=0)
            {
                if(G.vexs[t].length+G.arcs[t][k].info<=G.vexs[k].length)//减枝操作
                {
                    G.vexs[k].length=G.vexs[t].length+G.arcs[t][k].info;
                    q.push(G.vexs[k].data);
                }
                k=NextAdj(t,k);
            }
            q.pop();
        }
    }
     
    void Print()
    {
        for(int i=1;i<=G.vexnum;i++)
            printf("%d------%d\n",G.vexs[i].data,G.vexs[i].length);
    }
     
    int main()
    {
        CreateGraph();
        ShortestPaths(1);
        Print();
        return 0;
    }
    

    方法三:

    #include <iostream>
    #include<vector>
    #include<queue>
    using namespace std;
     
    typedef struct ArcCell{
        int u;//保存权值
        int info;//存储最短路径长度
        ArcCell(int a,int b):u(a),info(b){
    	}
    }ArcCell,AdjMaxtrix[100][100];
    
    typedef struct{
        int data;
        int length;
    }VerType;
     
    typedef struct{
        VerType vexs[100];//顶点向量
        vector<ArcCell>arcs[1001];
        int vexnum;//顶点数
        int arcnum;//弧数
    }Graph;
     
    Graph G;
    queue<int> q;
     
    void CreateGraph()
    {
        int m,n,t;
        printf("输入顶点数和弧数:");
        scanf("%d%d",&G.vexnum,&G.arcnum);
        printf("输入顶点:");
        for(int i=1;i<=G.vexnum;i++)
        {
            scanf("%d",&G.vexs[i].data);
            G.vexs[i].length=10000;
        }
        printf("输入弧及权重:\n");
        for(int i=1;i<=G.arcnum;i++)
            {
                scanf("%d%d%d",&m,&n,&t);
                G.arcs[m].push_back({n,t});
            }
     
    }
     
    void ShortestPaths(int v)
    {
        int k=0;//从首个节点开始访问
        int t;
        G.vexs[v].length=0;
        q.push(G.vexs[v].data);
        while(!q.empty())
        {
            t=q.front();
     		for(int i=0,j=G.arcs[t].size(); i<j; i++)
            {
            	
           	 	k=G.arcs[t][i].u; 
           	 	printf("%d------%d\n",t,k);
                if(G.vexs[t].length+G.arcs[t][i].info<=G.vexs[k].length)//减枝操作
                {
                    G.vexs[k].length=G.vexs[t].length+G.arcs[t][i].info;
                    q.push(G.vexs[k].data);
                }
               
            }
            q.pop();
        }
    }
     
    void Print()
    {
        for(int i=1;i<=G.vexnum;i++)
            printf("%d------%d\n",G.vexs[i].data,G.vexs[i].length);
    }
     
    int main()
    {
        CreateGraph();
        ShortestPaths(1);
        Print();
        return 0;
    }
    

     

    实验结果:

     

    心得与体会:

    算法分析:

    生成根节点的所有分支,全部入队列并记录路径;

    在队列中选择路径最短的分支作为扩展结点

    逐个生成分支,并判断分支的路径是否小于记录的最短路径;

    若不小于,舍弃该分支;

    若小于,该分支入队列;

    生成所有分支后,回到2;

    当队列为空时,算法结束。

     

    体会:

    1、  理解分支限界法的剪枝搜索策略;

    2、  掌握分支限界法的算法柜架;

    3、  掌握分支限界法的算法步骤;

    4、  通过应用范例学习动态规划算法的设计技巧与策略;

    5、  使用分支限界法解决单源最短路径问题。

     

    参考文章

    https://blog.csdn.net/weixin_44712386/article/details/105532881

    https://blog.csdn.net/gzj_1101/article/details/48955177

    https://www.jianshu.com/p/372dc2571784

    展开全文
  • 弗洛伊德算法(求最短路径) 在一个加权图中,如果想找到各个顶点之间的最短路径,可以考虑使用弗洛伊德算法。 弗洛伊德算法既适用于无向加权图,也适用于有向加权图。使用弗洛伊德算法查找最短路径时,只允许环路的...

    弗洛伊德算法(求最短路径)

    在一个加权图中,如果想找到各个顶点之间的最短路径,可以考虑使用弗洛伊德算法。

    弗洛伊德算法既适用于无向加权图,也适用于有向加权图。使用弗洛伊德算法查找最短路径时,只允许环路的权值为负数,其它路径的权值必须为非负数,否则算法执行过程会出错。

    弗洛伊德算法的实现思路

    弗洛伊德算法是基于动态规划算法实现的,接下来我们以在图 1 所示的有向加权图中查找各个顶点之间的最短路径为例,讲解弗洛伊德算法的实现思路。

    在这里插入图片描述

    图 1 有向加权图

    图 1 中不存在环路,且所有路径(边)的权值都为正数,因此可以使用弗洛伊德算法。

    弗洛伊德算法查找图 1 中各个顶点之间的最短路径,实现过程如下:

    1. 建立一张表格,记录每个顶点直达其它所有顶点的权值:

    表 1 各个顶点直达路径的权值

    目标顶点
    

    1 2 3 4
    起始顶点 1 0 3 ∞ 5
    2 2 0 ∞ 4
    3 ∞ 1 0 ∞
    4 ∞ ∞ 2 0

    起始顶点指的是从哪个顶点出发,目标顶点指的是要达到的顶点,例如 2->1 路径的权值是 2,顶点 2 是起始顶点,顶点 1 是目标顶点。此外,∞ 表示无穷大的数,即顶点之间不存在直达的路径。

    1. 在表 1 的基础上,将顶点 1 作为 “中间顶点”,计算从各个顶点出发途径顶点 1 再到达其它顶点的权值,如果比表 1 中记录的权值更小,证明两个顶点之间存在更短的路径,对表 1 进行更新。

    从各个顶点出发,途径顶点 1 再到达其它顶点的路径以及对应的权值分别是:

    2-1-3:权值为 2 + ∞ = ∞,表 1 中记录的 2-3 的权值也是 ∞;
    2-1-4:权值为 2 + 5 = 7,表 1 中记录的 2-4 的权值是 4;
    3-1-2:权值为 ∞ + 3,表 1 中记录的 3-2 的权值是 1;
    3-1-4:权值为 ∞ + 5,表 1 中记录的 3-4 的权值是 ∞;
    4-1-2:权值为 ∞ + 3,表 1 中记录的 4-2 的权值是 ∞;
    4-1-3:权值为 ∞ + ∞,表 1 中记录的 4-3 的权值是 2。

    以上所有的路径中,没有比表 1 中记录的权值最小的路径,所以不需要对表 1 进行更新。

    1. 在表 1 的基础上,以顶点 2 作为 “中间顶点”,计算从各个顶点出发途径顶点 2 再到达其它顶点的权值:

    1-2-3:权值为 3 + ∞,表 1 中记录的 1-3 的权值为 ∞;
    1-2-4:权值为 3 + 4 = 7,表 1 中 1-4 的权值为 5;
    3-2-1:权值为 1 + 2 = 3,表 1 中 3-1 的权值为 ∞,3 < ∞;
    3-2-4:权值为 1 + 4 = 5,表 1 中 3-4 的权值为 ∞,5 < ∞;
    4-2-1:权值为 ∞ + 2,表 1 中 4-1 的权值为 ∞;
    4-2-3:权值为 ∞ + ∞,表 1 中 4-3 的权值为 2。

    以顶点 2 作为 “中间顶点”,我们找到了比 3-1、3-4 更短的路径,对表 1 进行更新:

    表 2 更新后的 “表 1”

    目标顶点
    

    1 2 3 4
    起始顶点 1 0 3 ∞ 5
    2 2 0 ∞ 4
    3 3(3-2-1) 1 0 5(3-2-4)
    4 ∞ ∞ 2 0

    1. 在表 2 的基础上,将顶点 3 作为 “中间顶点”,计算从各个顶点出发途径顶点 3 再到达其它顶点的权值:

    1-3-2 权值为 ∞ + 1,表 2 中 1-2 的权值为 3;
    1-3-4 权值为 ∞ + 5,表 2 中 1-4 的权值为 5;
    2-3-1 权值为 ∞ + 3,表 2 中 2-1 的权值为 2;
    2-3-4 权值为 ∞ + 5,表 2 中 2-4 的权值为 4;
    4-3-1 权值为 2 + 3 = 5,表 2 中 4-1 的权值为 ∞,5 < ∞;
    4-3-2 权值为 2 + 1 = 3,表 2 中 4-2 的权值为 ∞,3 < ∞;

    以顶点 3 作为 “中间顶点”,我们找到了比 4-1、4-2 更短的路径,对表 2 进行更新:

    表 3 更新后的 “表 2”

    目标顶点
    

    1 2 3 4
    起始顶点 1 0 3 ∞ 5
    2 2 0 ∞ 4
    3 3(3-2-1) 1 0 5(3-2-4)
    4 5(4-3-2-1) 3(4-3-2) 2 0

    1. 在表 3 的基础上,将顶点 4 作为 “中间顶点”,计算从各个顶点出发途径顶点 4 再到达其它顶点的权值:

    1-4-2 权值为 5 + 3 = 8,表 3 中 1-2 的权值为 3;
    1-4-3 权值为 5 + 2 = 7,表 3 中 1-3 的权值为 ∞,7 < ∞;
    2-4-1 权值为 4 + 5 = 9,表 3 中 2-1 的权值为 2;
    2-4-3 权值为 4 + 2 = 6,表 3 中 2-3 的权值为 ∞,6 < ∞;
    3-4-1 权值为 4 + 5 = 9,表 3 中 3-1 的权值为 3;
    3-4-2 权值为 5 + 5 = 10 ,表 3 中 3-2 的权值为 1。

    以顶点 4 作为 “中间顶点”,我们找到了比 1-3、2-3 更短的路径,对表 3 进行更新:

    表 4 更新后的 “表 3”

    目标顶点
    

    1 2 3 4
    起始顶点 1 0 3 7(1-4-3) 5
    2 2 0 6(2-4-3) 4
    3 3(3-2-1) 1 0 5(3-2-4)
    4 5(4-3-2-1) 3(4-3-2) 2 0
    通过将所有的顶点分别作为“中间顶点”,最终得到的表 4 就记录了各个顶点之间的最短路径。例如,4-1 的最短路径为 4-3-2-1。

    弗洛伊德算法的具体实现

    了解了弗洛伊德算法查找最短路径的实现思路后,接下来仍以图 1 为例,分别编写 C、Java、Python 程序实现弗洛伊德算法。

    如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 C 语言程序:

    #include <stdio.h>
    #define V 4    //设定图中的顶点数
    #define INF 65535   // 设置一个最大值
    int P[V][V] = { 0 }; //记录各个顶点之间的最短路径
    void printMatrix(int matrix[][V]);  //输出各个顶点之间的最短路径
    void printPath(int i, int j); // 递归输出各个顶点之间最短路径的具体线路
    void floydWarshall(int graph[][V]); // 实现弗洛伊德算法
    int main() {
        // 有向加权图中各个顶点之间的路径信息
        int graph[V][V] = { {0, 3, INF, 5},
                              {2, 0, INF, 4},
                              {INF, 1, 0, INF},
                              {INF, INF, 2, 0} };
        floydWarshall(graph);
    }
    // 中序递归输出各个顶点之间最短路径的具体线路
    void printPath(int i, int j)
    {
        int k = P[i][j];
        if (k == 0)
            return;
        printPath(i, k);
        printf("%d-", k + 1);
        printPath(k, j);
    }
    // 输出各个顶点之间的最短路径
    void printMatrix(int graph[][V]) {
        int i, j;
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (j == i) {
                    continue;
                }
                printf("%d - %d: 最短路径为:", i + 1, j + 1);
                if (graph[i][j] == INF)
                    printf("%s\n", "INF");
                else {
                    printf("%d", graph[i][j]);
                    printf(",依次经过:%d-", i + 1);
                    //调用递归函数
                    printPath(i, j);
                    printf("%d\n", j + 1);
                }
            }
        }
    }
    // 实现弗洛伊德算法,graph[][V] 为有向加权图
    void floydWarshall(int graph[][V]) {
        int  i, j, k;
        //遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组
        for (k = 0; k < V; k++) {
            for (i = 0; i < V; i++) {
                for (j = 0; j < V; j++) {
                    //如果新的路径比之前记录的更短,则更新 graph 数组
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                        //记录此路径
                        P[i][j] = k;
                    }
                }
            }
        }
        // 输出各个顶点之间的最短路径
        printMatrix(graph);
    }
    
    

    如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 Java 程序:

    public class Floyd {
        static int V = 4; // 顶点的个数
        static int[][] P = new int[V][V]; // 记录各个顶点之间的最短路径
        static int INF = 65535; // 设置一个最大值
        // 中序递归输出各个顶点之间最短路径的具体线路
        public static void printPath(int i, int j) {
            int k = P[i][j];
            if (k == 0)
                return;
            printPath(i, k);
            System.out.print((k + 1) + "-");
            printPath(k, j);
        }
        // 输出各个顶点之间的最短路径
        public static void printMatrix(int[][] graph) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (j == i) {
                        continue;
                    }
                    System.out.print((i + 1) + " - " + (j + 1) + ":最短路径为:");
                    if (graph[i][j] == INF)
                        System.out.println("INF");
                    else {
                        System.out.print(graph[i][j]);
                        System.out.print(",依次经过:" + (i + 1) + "-");
                        // 调用递归函数
                        printPath(i, j);
                        System.out.println((j + 1));
                    }
                }
            }
        }
        // 实现弗洛伊德算法,graph[][V] 为有向加权图
        public static void floydWarshall(int[][] graph) {
            int i, j, k;
            // 遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组
            for (k = 0; k < V; k++) {
                for (i = 0; i < V; i++) {
                    for (j = 0; j < V; j++) {
                        // 如果新的路径比之前记录的更短,则更新 graph 数组
                        if (graph[i][k] + graph[k][j] < graph[i][j]) {
                            graph[i][j] = graph[i][k] + graph[k][j];
                            // 记录此路径
                            P[i][j] = k;
                        }
                    }
                }
            }
            // 输出各个顶点之间的最短路径
            printMatrix(graph);
        }
        public static void main(String[] args) {
            // 有向加权图中各个顶点之间的路径信息
            int[][] graph = new int[][] { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
            floydWarshall(graph);
        }
    }
    
    
    

    如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 Python 程序:

    V = 4   # 顶点的个数
    INF = 65535    # 设定一个最大值
    P = [[0]*V for i in range(V)] # 记录各个顶点之间的最短路径
    # 有向加权图中各个顶点之间的路径信息
    graph = [[0, 3, INF, 5],
             [2, 0, INF, 4],
             [INF, 1, 0, INF],
             [INF, INF, 2, 0]]
    # 中序递归输出各个顶点之间最短路径的具体线路
    def printPath(i,j):
        k = P[i][j]
        if k == 0:
            return;
        printPath(i , k)
        print("%d-" % (k + 1) , end='')
        printPath(k , j)
    # 输出各个顶点之间的最短路径
    def printMatrix(graph):
        for i in range(V):
            for j in range(V):
                if j == i:
                    continue
                print("%d - %d: 最短路径为:"%(i + 1, j + 1) , end='')
                if graph[i][j] == INF:
                    print("INF")
                else:
                    print(graph[i][j] , end='')
                    print(",依次经过:%d-"%(i+1) , end='')
                    # 调用递归函数
                    printPath(i , j)
                    print(j + 1)
    # 实现弗洛伊德算法,graph[][V] 为有向加权图
    def floydWarshall(graph):
        # 遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组
        for k in range(V):
            for i in range(V):
                for j in range(V):
                    # 如果新的路径比之前记录的更短,则更新 graph 数组
                    if graph[i][k] + graph[k][j] < graph[i][j]:
                        graph[i][j] = graph[i][k] + graph[k][j]
                        # 记录此路径
                        P[i][j] = k
        # 输出各个顶点之间的最短路径
        printMatrix(graph)
    floydWarshall(graph)
    

    以上程序的输出结果均为:
    1 - 2: 最短路径为:3,依次经过:1-2
    1 - 3: 最短路径为:7,依次经过:1-4-3
    1 - 4: 最短路径为:5,依次经过:1-4
    2 - 1: 最短路径为:2,依次经过:2-1
    2 - 3: 最短路径为:6,依次经过:2-4-3
    2 - 4: 最短路径为:4,依次经过:2-4
    3 - 1: 最短路径为:3,依次经过:3-2-1
    3 - 2: 最短路径为:1,依次经过:3-2
    3 - 4: 最短路径为:5,依次经过:3-2-4
    4 - 1: 最短路径为:5,依次经过:4-3-2-1
    4 - 2: 最短路径为:3,依次经过:4-3-2
    4 - 3: 最短路径为:2,依次经过:4-3

    展开全文
  • javafx-最短路径挑战 最短路径挑战 该应用程序将生成一个像素网格。 在网格内,将有一组节点。 一个节点代表网格上的一个像素。 节点由其节点编号唯一标识,并且它在网格中的位置由 (x,y) 坐标表示。 您的挑战是...
  • 数据结构的树和图章节的最短路径源代码 可以运行
  • AE+C#最短路径程序

    2013-03-10 15:22:24
    AE和C#开发的最短路径程序,解压后可直接运行,自带数据,选择目标点后,在地图上高亮显示最短路径.
  • c语言,迷宫最短路径

    2021-05-19 18:27:48
    #include #include #include #define MAX 30//迷宫最大30*30#define ENDS -2//端点位置标记为-2#define ROUT -1//入队的路径标记为-1#define SHORTESTPATH 2//将最终的最短路径标记为2//队列结构,保存进行广度优先...

    #include

    #include

    #include

    #define MAX 30//迷宫最大30*30

    #define ENDS -2//端点位置标记为-2

    #define ROUT -1//入队的路径标记为-1

    #define SHORTESTPATH 2//将最终的最短路径标记为2

    //队列结构,保存进行广度优先搜索时的路径

    typedef struct QueueNode

    {

    int a[2];//记录当前对应的位置

    int source;//记录新节点是由哪个节点探测的

    int self;//记录新节点在队列中的位置

    struct QueueNode *parent,*next;//双亲域

    }Queue;

    Queue *front;//队头指针

    Queue *rear;//队尾指针

    //栈结构,保存已经探测好的路径

    typedef struct Path

    {

    int a[2];

    struct Path *next;

    }PathStack;

    int MapRand(int i,int j,int maze[MAX][MAX])//随机迷宫生成函数,百分之六十是墙,百分之四十是通路

    {

    float scale=0.4;//墙的比例,百分之六十

    int count=0;//计数器,在对迷宫比例进行局部调整的时候使用

    time_t t;//设定时间种子

    srand((unsigned)time(&t));

    int m,n;//控制循环变量

    for(m=0;m

    for(n=0;n

    maze[m][n]=rand()%10;

    for(m=0;m

    for(n=0;n

    if(maze[m][n]<5)

    maze[m][n]=0;

    else

    maze[m][n]=1;

    //控制墙和路的比例

    for(n=0;n

    {

    maze[0][n]=0;

    maze[i-1][n]=0;

    }

    for(m=1;m

    {

    maze[m][0]=0;

    maze[m][j-1]=0;

    }

    //将外围置为墙,防止出界

    for(m=1;m

    for(n=1;n

    if(maze[m][n]==0)

    count++;

    //统计墙的个数

    int total;//墙的总数

    total=(int)(i-2)*(j-2)*scale;

    while(count!=total)

    if(count

    {

    m=rand()%(i-2)+1;

    n=rand()%(j-2)+1;

    if(maze[m][n]==1)

    {

    maze[m][n]=0;

    count++;

    }

    }

    else

    {

    m=rand()%(i-2)+1;

    n=rand()%(j-2)+1;

    if(maze[m][n]==0)

    {

    maze[m][n]=1;

    count--;

    }

    }

    //对迷宫进行局部随机调整,使墙和路的比例合乎规定

    return 0;

    }

    int PrintMap(int i,int j,int maze[MAX][MAX])//打印迷宫

    {

    int m,n;

    printf(" ");

    for(n=0;n

    printf("%d",n%10);

    printf("\n");

    for(m=0;m

    {

    printf("%d",m%10);

    for(n=0;n

    {

    if(maze[m][n]==0)

    printf("%c",219);

    //墙

    if(maze[m][n]==1||maze[m][n]==ROUT)

    printf(" ");

    if(maze[m][n]==SHORTESTPATH)

    printf("*");

    //路径

    if(maze[m][n]==ENDS)

    printf("%c",1);//笑脸

    //开始位置和终点位置

    }

    printf("\n");

    }

    printf("\n");

    return 0;

    }

    int InitQueue(int maze[MAX][MAX])//构造一个队列,并把起始位置加入队列

    {

    int m,n;//起始位置坐标

    printf("Please enter the starting location(i,j):");

    scanf("%d%d",&m,&n);

    getchar();

    while(maze[m][n]==0)

    {

    printf("This seat is unacceptable,please reenter the starting location(i,j):");

    scanf("%d%d",&m,&n);

    getchar();

    }

    maze[m][n]=ENDS;//开始位置

    Queue *q;

    q=(Queue *)malloc(sizeof(Queue));

    if(q==NULL)

    {

    printf("Error1!");

    exit(1);

    }

    q->a[0]=m;

    q->a[1]=n;

    q->parent=q->next=NULL;

    q->source=0;

    q->self=0;

    front=rear=q;

    return 0;

    }

    int EnQueue(int m,int n)//入队函数

    {

    Queue *q;

    q=(Queue *)malloc(sizeof(Queue));

    if(q==NULL)

    {

    printf("Error2!");

    exit(1);

    }

    q->a[0]=m;

    q->a[1]=n;

    q->next=NULL;

    q->self=rear->self+1;

    q->source=front->self;

    rear->next=q;

    q->parent=rear;

    rear=q;

    return 0;

    }

    PathStack *pushstack(PathStack *top,int m,int n)//入栈函数

    {

    PathStack *q;

    q=(PathStack *)malloc(sizeof(PathStack));

    if(q==NULL)

    {

    printf("Error3!");

    exit(1);

    }

    q->a[0]=m;

    q->a[1]=n;

    q->next=top;

    top=q;

    return top;

    }

    int ShortestPath_BFS(int maze[MAX][MAX])//广度优先搜索,寻找最短路径

    {

    int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//四个方向,依次是右,下,左,上

    int i;//控制循环变量,实现四个方向的转换

    int m,n;//记录坐标位置,用此位置来探测下一位置

    int end1,end2;//终点坐标位置

    printf("please enter the end position(i,j):");

    scanf("%d%d",&end1,&end2);

    getchar();

    while(maze[end1][end2]==0)

    {

    printf("This seat is unacceptable,please reenter the end position(i,j):");

    scanf("%d%d",&end1,&end2);

    getchar();

    }

    while(front)

    {

    m=front->a[0];

    n=front->a[1];

    for(i=0;i<4;i++)

    {

    int x,y;

    x=m+move[i][0];

    y=n+move[i][1];

    if(maze[x][y]==1)

    {

    maze[x][y]=ROUT;//将入队的位置标记为-1

    EnQueue(x,y);

    if(x==end1&&y==end2)

    return 0;

    }

    }

    front=front->next;

    }

    printf("Sorry,No can reach path!\n");

    return 1;

    }

    PathStack * Shortestpath(PathStack *top,int maze[MAX][MAX])//用栈结构保存路径

    {

    int m,n;//记录指针对应的位置

    int t;//记录该位置的来源,即由哪个节点探测的

    Queue *p=rear;

    m=p->a[0];

    n=p->a[1];

    top=pushstack(top,m,n);

    maze[m][n]=ENDS;

    t=p->source;

    while(1)

    {

    p=p->parent;

    if(p->self==t)

    break;

    }

    while(p->parent)

    {

    m=p->a[0];

    n=p->a[1];

    maze[m][n]=SHORTESTPATH;

    top=pushstack(top,m,n);

    t=p->source;

    while(1)

    {

    p=p->parent;

    if(p->self==t)

    break;

    }

    }

    m=p->a[0];

    n=p->a[1];

    maze[m][n]=ENDS;

    top=pushstack(top,m,n);

    return top;

    }

    int PrintPath(PathStack *top,PathStack *base)//打印路径

    {

    int k=0;//控制输出格式

    int m,n;//迷宫位置

    m=top->a[0];

    n=top->a[1];

    printf("(%d,%d)%c",m,n,26);

    k++;

    top=top->next;

    while(top->next!=base)

    {

    m=top->a[0];

    n=top->a[1];

    printf("(%d,%d)%c",m,n,26);

    k++;

    if(k==5)

    {

    printf("\n");

    k=0;

    }

    top=top->next;

    }

    m=top->a[0];

    n=top->a[1];

    printf("(%d,%d)\n",m,n);

    return 0;

    }

    int main()

    {

    int maze[MAX][MAX];

    int i,j;//i行数,j列数

    PathStack head;

    head.next=NULL;

    PathStack *top;

    top=&head;

    //初始化栈结构

    while(1)

    {

    char c;

    printf("InitMap:I,PrintMap:P,SearchShortestpath:S,Route:R,Quit:Q:");

    scanf("%c",&c);

    getchar();

    if(c=='I'||c=='i')//初始化地图

    {

    printf("Please Enter The Line Number(<=30) And Column Number(<=30):");

    scanf("%d%d",&i,&j);

    getchar();

    while(i>30||j>30)

    {

    printf("Please Enter The Line Number(<=30) And Column Number(<=30):");

    scanf("%d%d",&i,&j);

    getchar();

    }

    MapRand(i,j,maze);

    //以上为创建随机迷宫

    }

    else if(c=='P'||c=='p')//打印地图

    PrintMap(i,j,maze);

    else if(c=='S'||c=='s')

    {

    InitQueue(maze);//初始化队列

    if(ShortestPath_BFS(maze)==1)//如果返回值为1,则说明没有可通路径,退出函数

    continue;

    top=Shortestpath(top,maze);

    }

    else if(c=='R'||c=='r')//打印路径

    PrintPath(top,&head);

    else if(c=='Q'||c=='q')//退出程序

    return 0;

    fflush(stdin);//清空缓冲区

    }

    return 0;

    }

    运行结果:

    0818b9ca8b590ca3270a3433284dd417.png

    展开全文
  • 单源最短路径算法c++实现(贪心算法)
  • 用gtk+2.0开发的一个小程序,用来显示最短路径,前台界面用gtk+2.0开发,后台用flody算法,支持手工画图,动态修改图的结构,包括修改顶点、边长等等,可以在界面上显示任意两点之间的最短路径,可以在图上画出来,...
  • 运行程序 python spsolve.py --infile input_file --output outfile or python spsolve.py To use stdin and stdout 输入格式 输入采用 DIMACS 格式,可以使用生成。 DIMACS 格式是面向行的。 一行包含的记录类型...
  • 最短路径python

    2020-11-29 17:22:44
    最短路径问题(python实现)解决最短路径问题:(如下三种算法)(1)迪杰斯特拉算法(dijkstra算法)(2)弗洛伊德算法(floyd算法) (3)spfa算法第一种算法:dijkstra算法广度优先搜索解决赋权有向图或者无向图...
  • 此应用程序可让您从 Cytoscape 中的给定图形创建生成树和所有配对最短路径。 去做 自述文件 此自述文件通常会记录启动和运行应用程序所需的任何步骤。 这个存储库是做什么用的? 快速总结 版本 我
  • 求解城市之间的最短距离是一个非常实际的问题,其大意如下:某地区由n个城市,如何选择路线使...1.最短路径算法//最短路径算法static void distMin(GraphMatrix GM,int vend){ //vend为结束点int[] weight=new in...
  • 这是一个python程序,它将使用蚁群优化算法找到访问所有点的最短路径 这是如何工作的 现在这只能生成随机的点集,但我希望给它一种能力,以便找到一次访问所有点的最短路径 如何使用 1-将此仓库克隆到您的PC 要使用...
  • 2.求城市D到其他城市的最短路径,及其最小代价 3.可视化表示最短路径 矩阵mat如下。99999表示不可达 0 12 99999 99999 99999 16 14 12 0 10 99999 99999 7 99999 99999 10 0 3 5 6 99999 99999 99999 3 0 4 99999 ...
  • spf算法(spf算法计算最短路径)

    千次阅读 2021-07-06 01:29:55
    SPF算法有时也被称为Dijkstra算法,这是因为最短路径优先算法SPF是Dijkstra发明的。SPF算法将每一个路由器作为根(ROOT)来计. SPF算法是OSPF路由协议的基础;DUAL(扩散更新)算法被EIGRP路由协议采用。介绍下:四...
  • 1、目 录 一、概述1二、系统分析1三、概要设计2四、详细设计54.1建立图的存储结构54.2单源最短路径64.3任意一对顶点之间的最短路径7五、运行与测试8参考文献11附录12交通咨询系统设计(最短路径问题)一、概述 在交通...
  • 查找最短路径

    2020-12-16 23:07:54
    通过迪杰斯特拉算法查找任意可达两点之间的最短路径 文章目录前言一、运行展示二、功能展示三、源码展示 前言 这是博主在校学习数据结构时所写的程序,通过展示学校主要地点来使用迪杰斯特拉算法实现求任意可达两...
  • 第八十五天 --- 图论最短路径专题(力扣743、5888)题目一朴素Dijkstra解决无负权边的单源最短路径问题思路代码邻接矩阵邻接表复杂度Floyd解决多源点最短路径问题题目二堆优化Dijkstra解决无负权边的单源最短路径...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,481
精华内容 15,392
关键字:

最短路径程序运行