算法——无向图的最短路径算法

2023-10-30

https://www.jb51.net/article/154796.htm

我是看上面的文章写的程序，他的第一种解法还需要我再理解理解！！

BFS一层层寻找目标节点的算法

思路：

1.先从v到u的使用BFS遍历一遍图，得到每个节点到v的最短距离，使用数组first记录；

2.再从v到u的使用BFS遍历一遍图，得到每个节点到u的最短距离leastpath，同时判断first[v]-每一个节点的leastpath，看是否等于每一个节点对应的first数组的值。

3.如果相等，说明当前节点是最小路径的其中一个节点，但是当前算法也有缺憾，就是如果u与v之间有多条最短路径。那么就会出错，这个BUG我目前没有想出解决的办法。

下面程序只能计算无向无权图的一条最短路径，并且该图有且只能有一条最短路径！！很拉跨！

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//边表节点
typedef struct ArcNode
{
    int Adjvex;
    ArcNode*next=nullptr;
    ArcNode(int x,ArcNode*p):Adjvex(x),next(p) {}
} ArcNode;
//顶点表节点
typedef struct VerNode
{
    int Vervex;
    ArcNode*First_Edge;
    VerNode(int x,ArcNode*p):Vervex(x),First_Edge(p) {}
} VerNode;
class chart
{
private:
    vector<VerNode*>VerNode_List;
    vector<int>Visited_Mark;
public:
    chart() {}
    void make(vector<int>data,int Road_Nums);
    void Print();
    void BFS(int v,int u);
    void Reset();
    ~chart();
};
void chart::make(vector<int>data,int Road_Nums)
{
    VerNode*Node_Pointer_temp;
    ArcNode*Arc_Pointer;
    int i,j,k;
    int Data_Len=data.size();
    for(i=0; i<Data_Len; i++)
    {
        Node_Pointer_temp=new VerNode(data[i],nullptr);
        VerNode_List.push_back(Node_Pointer_temp);
        Visited_Mark.push_back(0);
    }
    for(k=0; k<Road_Nums; k++)
    {
        cout<<"请输入无向图的路径i——j"<<endl;
        cout<<"请输入i:  ";
        cin>>i;
        cout<<endl<<"请输入j:  ";
        cin>>j;
        cout<<endl;
        Arc_Pointer=new ArcNode(j,VerNode_List[i]->First_Edge);
        VerNode_List[i]->First_Edge=Arc_Pointer;
        Arc_Pointer=new ArcNode(i,VerNode_List[j]->First_Edge);
        VerNode_List[j]->First_Edge=Arc_Pointer;
    }
}
void chart::Print()
{
    ArcNode*s;
    int i;
    for(i=0; i<VerNode_List.size(); i++)
    {
        //cout<<VerNode_List[i]->Vervex;
        s=VerNode_List[i]->First_Edge;
        while(s!=nullptr)
        {
            cout<<" "<<VerNode_List[i]->Vervex<<"——"<<s->Adjvex<<" ";
            s=s->next;
        }
        cout<<endl;
    }
}
chart::~chart()
{
    ArcNode*s;
    ArcNode*q;
    int i;
    for(i=0; i<VerNode_List.size(); i++)
    {
        s=VerNode_List[i]->First_Edge;
        delete VerNode_List[i];
        while(s!=nullptr)
        {
            q=s;
            s=s->next;
            delete q;
        }
    }
}
void chart::BFS(int v,int u)
{
    int node=VerNode_List.size();

    //第一遍遍历时，存储各个节点到v节点的最短路径长度
    vector<int>first(node);
    //v节点到自身的距离为0
    first[v]=0;

    VerNode*t;//定点表指针
    ArcNode*tu;//边表指针
    int idx;//记录相连节点下标

    queue<VerNode*>op;
    int q_len;//队列长度

    Visited_Mark[v]=1;
    op.push(VerNode_List[v]);

    int floor=0;//记录离源点的最小层数

    while(!op.empty())
    {
        q_len=op.size();
        floor++;
        for(int i=0; i<q_len; i++)
        {
            t=op.front();
            op.pop();
            for(tu=t->First_Edge; tu!=nullptr; tu=tu->next)
            {
                idx=tu->Adjvex;
                if(Visited_Mark[idx]!=1)
                {
                    Visited_Mark[idx]=1;
                    first[idx]=floor;
                    op.push(VerNode_List[idx]);
                }
            }
        }
    }

    //第一次层序遍历没有问题
    cout<<endl<<"我先打印一下最短的路径长度："<<first[u]<<endl;


    //重置节点状态
    Reset();
    floor=0;
    //存储最短路径的数组
    vector<int>res;
    res.push_back(u);
    //再从u开始往回遍历
    Visited_Mark[u]=1;
    op.push(VerNode_List[u]);
     while(!op.empty())
    {
        q_len=op.size();
        floor++;
        for(int i=0; i<q_len; i++)
        {
            t=op.front();
            op.pop();
            for(tu=t->First_Edge; tu!=nullptr; tu=tu->next)
            {
                idx=tu->Adjvex;
                if(Visited_Mark[idx]!=1)
                {
                    Visited_Mark[idx]=1;
                    op.push(VerNode_List[idx]);
                    if((first[u]-floor)==first[idx])
                    {
                        res.push_back(idx);
                    }
                }
            }
        }
    }
    for(int i=0;i<res.size();i++)
        cout<<res[i]<<" ";
}
void chart::Reset()
{
    int i=0;
    for(i=0; i<Visited_Mark.size(); i++)
        Visited_Mark[i]=0;
}
int main()
{
    vector<int>qaq= {0,1,2,3,4,5,6,7};
    chart wow;
    wow.make(qaq,9);
    wow.Print();
    wow.BFS(0,2);
    return 0;
}

运行截图：

目前使用DFS，BFS遍历出所有路径的方法，以及Dijkstra,Floyd算法来求得最短路径的方法还不会，以及上面这段程序还有BUG要更改！！

下面是使用Dijkstra算法来对一个带权无向图进行计算最短路径，不带权的图直接就可以把所有弧的权值设置为1，同样可以计算。

Dijkstra算法

思路：

1.从一个单源节点开始计算，寻找当前节点周围没有遍历过的邻接点，并且把当前单源节点设置为以访问状态；

2.如果从当前节点到这些邻接点的距离更短，那么更新这些邻接点的父节点数组为当前节点，距离数组为当前节点的距离数组+这些邻接点与当前节点之间弧的权重；

3.并且在遍历当前节点的邻接点的时候，要选出当前节点与这些邻接点之间弧权重最短的那个邻接点作为下一次的单源节点；

4.对下一次的单元节点的操作与上面操作类似；

5.以上操作需要借助队列来实现。

代码：

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
//边表节点
typedef struct ArcNode
{
    int Adjvex;
    ArcNode*next=nullptr;
    int wet;
    ArcNode(int x,ArcNode*p,int y):Adjvex(x),next(p),wet(y) {}
} ArcNode;
//顶点表节点
typedef struct VerNode
{
    int Vervex;
    ArcNode*First_Edge;
    VerNode(int x,ArcNode*p):Vervex(x),First_Edge(p) {}
} VerNode;
class chart
{
private:
    vector<VerNode*>VerNode_List;//存储图的每一个节点数据
    vector<int>Visited_Mark;//存储访问数据的情况

    vector<int>Parent;//存储节点的上一个父亲节点
    vector<int>Distance;//存储源节点到每一个节点的最短距离
public:
    chart() {}
    void make(vector<int>data,int Road_Nums);
    void Print();
    void BFS(int v,int u);//这是一个对无权最短路径计算不完全的算法，很有局限性
    void Reset();
    void Dijkstra(int u);
    ~chart();
};
void chart::make(vector<int>data,int Road_Nums)
{
    VerNode*Node_Pointer_temp;
    ArcNode*Arc_Pointer;
    int i,j,k,w;
    int Data_Len=data.size();
    for(i=0; i<Data_Len; i++)
    {
        Node_Pointer_temp=new VerNode(data[i],nullptr);
        VerNode_List.push_back(Node_Pointer_temp);
        Visited_Mark.push_back(0);
        Parent.push_back(-1);
        Distance.push_back(INT_MAX);
    }
    for(k=0; k<Road_Nums; k++)
    {
        cout<<"请输入无向图的路径i——j，以及权重"<<endl;
        cout<<"请输入i:  ";
        cin>>i;
        cout<<endl<<"请输入j:  ";
        cin>>j;
        cout<<endl<<"请输入i——j之间弧的权重";
        cin>>w;
        cout<<endl;
        Arc_Pointer=new ArcNode(j,VerNode_List[i]->First_Edge,w);
        VerNode_List[i]->First_Edge=Arc_Pointer;
        Arc_Pointer=new ArcNode(i,VerNode_List[j]->First_Edge,w);
        VerNode_List[j]->First_Edge=Arc_Pointer;
    }
}
void chart::Print()
{
    ArcNode*s;
    int i;
    for(i=0; i<VerNode_List.size(); i++)
    {
        //cout<<VerNode_List[i]->Vervex;
        s=VerNode_List[i]->First_Edge;
        while(s!=nullptr)
        {
            cout<<" "<<VerNode_List[i]->Vervex<<"——"<<s->Adjvex<<" ";
            s=s->next;
        }
        cout<<endl;
    }
}
chart::~chart()
{
    ArcNode*s;
    ArcNode*q;
    int i;
    for(i=0; i<VerNode_List.size(); i++)
    {
        s=VerNode_List[i]->First_Edge;
        delete VerNode_List[i];
        while(s!=nullptr)
        {
            q=s;
            s=s->next;
            delete q;
        }
    }
}
void chart::BFS(int v,int u)//说实话，这段算法其实很有局限性嗷
{
    int node=VerNode_List.size();

    //第一遍遍历时，存储各个节点到v节点的最短路径长度
    vector<int>first(node);
    //v节点到自身的距离为0
    first[v]=0;

    VerNode*t;//定点表指针
    ArcNode*tu;//边表指针
    int idx;//记录相连节点下标

    queue<VerNode*>op;
    int q_len;//队列长度

    Visited_Mark[v]=1;
    op.push(VerNode_List[v]);

    int floor=0;//记录离源点的最小层数

    while(!op.empty())
    {
        q_len=op.size();
        floor++;
        for(int i=0; i<q_len; i++)
        {
            t=op.front();
            op.pop();
            for(tu=t->First_Edge; tu!=nullptr; tu=tu->next)
            {
                idx=tu->Adjvex;
                if(Visited_Mark[idx]!=1)
                {
                    Visited_Mark[idx]=1;
                    first[idx]=floor;
                    op.push(VerNode_List[idx]);
                }
            }
        }
    }

    //第一次层序遍历没有问题
    cout<<endl<<"我先打印一下最短的路径长度："<<first[u]<<endl;


    //重置节点状态
    Reset();
    floor=0;
    //存储最短路径的数组
    vector<int>res;
    res.push_back(u);
    //再从u开始往回遍历
    Visited_Mark[u]=1;
    op.push(VerNode_List[u]);
     while(!op.empty())
    {
        q_len=op.size();
        floor++;
        for(int i=0; i<q_len; i++)
        {
            t=op.front();
            op.pop();
            for(tu=t->First_Edge; tu!=nullptr; tu=tu->next)
            {
                idx=tu->Adjvex;
                if(Visited_Mark[idx]!=1)
                {
                    Visited_Mark[idx]=1;
                    op.push(VerNode_List[idx]);
                    if((first[u]-floor)==first[idx])
                    {
                        res.push_back(idx);
                    }
                }
            }
        }
    }
    cout<<"最短路径"<<endl;
    for(int i=0;i<res.size();i++)
        cout<<res[i]<<" ";
}
void chart::Reset()
{
    int i=0;
    for(i=0; i<Visited_Mark.size(); i++)
    {
        Visited_Mark[i]=0;
        Parent[i]=-1;
        Distance[i]=INT_MAX;
    }
}
void chart::Dijkstra(int u)
{
    int node=Parent.size();//节点数
    queue<VerNode*> s;

    s.push(VerNode_List[u]);
    Parent[u]=-1;
    Distance[u]=0;

    while(!s.empty())
    {
        int idx=s.front()->Vervex;
        Visited_Mark[idx]=1;
        int last=-1;//记录最后要入队的那个节点的下标
        int last_wt=INT_MAX;
        for(ArcNode*p=VerNode_List[idx]->First_Edge;p!=nullptr;p=p->next)
        {
            int pls=p->Adjvex;
            if(Visited_Mark[pls]==0)//没有被访问过
            {
                if(((p->wet)+Distance[idx])<Distance[pls])
                {
                    Distance[pls]=((p->wet)+Distance[idx]);
                    Parent[pls]=idx;
                }
                if((p->wet)<last_wt)
                {
                    last=pls;
                    last_wt=(p->wet);
                }
            }
        }
        if(last!=-1)//如果最终选中的节点下标等于-1，那么说明没有与当前节点相连的节点了
        {
            s.push(VerNode_List[last]);
        }
        s.pop();
    }
    cout<<endl<<"当前的源节点是"<<u<<endl;
    //打印出各个数组存储的数据

    cout<<"Distance数组："<<endl;
    for(int i=0;i<node;i++)
    {
        cout<<Distance[i]<<" ";
    }
    cout<<endl<<"Parent数组："<<endl;
    for(int i=0;i<node;i++)
    {
        cout<<Parent[i]<<" ";
    }
}
int main()
{
    vector<int>qaq= {0,1,2,3,4,5,6,7,8};
    chart wow;
    wow.make(qaq,14);
    wow.Print();
    wow.BFS(0,4);
    wow.Reset();
    wow.Dijkstra(0);
    return 0;
}

选择测试的无向图：

程序运行：

最后，果然我第一次写的函数在这个无向图翻车了……

具有很强的局限性啊！

建议学习DIjkstra算法和Floyd算法时，看这个视频

https://www.bilibili.com/video/BV1q4411M7r9?from=search&seid=9662298119837732890

思路：

1.使用两个n*n的矩阵Dist，Plain（n是节点的个数），Dist是i节点到j节点的最短距离，Plain存放的是i到j最短路径的节点遍历顺序，

比如Plain[i][j]=k,那么从i到j的最短路径就要经过k节点，那么就去Plain[k][j]查看Plain[k][j]的值是否为j，如果为，那么最短路径就是

i->k->j,否则就继续像之前那样寻找最短路径上的节点。

2.初始换Dist数组，其实就是把邻接表转换成邻接矩阵，从而更好操作，主对角线由于图中弧权重可为负数，所以主对角线上可以初始化为一个极大或者极小的值，然后不相通的两个节点的Dist不能直接设置为INT_MAX,在这上面我吃了大亏，他会整型越界,最好设置为INT_MAX-50。

3.初始化Plain数组，Plain[i][j]初始化为j，而当i==j的时候，初始化为-1，因为节点中没有-1为下标。

4.然后使用三层循环，最外层的k循环，是循环遍历中间节点，内两层循环更新距离数组，如果i先到k这个中间节点在到j节点比之前其他路径更短，那么同时更新路径数组，和顺序数组，很重要的一点在更新的时候，下标为k的行和列以及对角线不参与这种更新。

5.最后还有更加重要的一点就是如果i无法到达k的话，就不能更新，因为当k到j的弧的权重为负数的话就会发生非常不好的结果，我深有体会！

6.和有向图的一样，可以理解为两个节点之间有两条互相指向的弧且权重相等，不过图中弧如果有负数，会出现一种极其骚的情况就是来回绕！！很迷……所以Floyd可能不适合无向图。

代码：

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
//边表节点
typedef struct ArcNode
{
    int Adjvex;
    ArcNode*next=nullptr;
    int wet;
    ArcNode(int x,ArcNode*p,int y):Adjvex(x),next(p),wet(y) {}
} ArcNode;
//顶点表节点
typedef struct VerNode
{
    int Vervex;
    ArcNode*First_Edge;
    VerNode(int x,ArcNode*p):Vervex(x),First_Edge(p) {}
} VerNode;
class chart
{
private:
    vector<VerNode*>VerNode_List;//存储图的每一个节点数据
    vector<int>Visited_Mark;//存储访问数据的情况

    vector<int>Parent;//存储节点的上一个父亲节点
    vector<int>Distance;//存储源节点到每一个节点的最短距离
public:
    chart() {}
    void make(vector<int>data,int Road_Nums);
    void Print();
    void BFS(int v,int u);//这是一个对无权最短路径计算不完全的算法，很有局限性
    void Reset();
    void Dijkstra(int u);
    void Floyd();
    ~chart();
};
void chart::make(vector<int>data,int Road_Nums)
{
    VerNode*Node_Pointer_temp;
    ArcNode*Arc_Pointer;
    int i,j,k,w;
    int Data_Len=data.size();
    for(i=0; i<Data_Len; i++)
    {
        Node_Pointer_temp=new VerNode(data[i],nullptr);
        VerNode_List.push_back(Node_Pointer_temp);
        Visited_Mark.push_back(0);
        Parent.push_back(-1);
        Distance.push_back(INT_MAX);
    }
    for(k=0; k<Road_Nums; k++)
    {
        cout<<"请输入无向图的路径i——j，以及权重"<<endl;
        cout<<"请输入i:  ";
        cin>>i;
        cout<<endl<<"请输入j:  ";
        cin>>j;
        cout<<endl<<"请输入i——j之间弧的权重";
        cin>>w;
        cout<<endl;
        Arc_Pointer=new ArcNode(j,VerNode_List[i]->First_Edge,w);
        VerNode_List[i]->First_Edge=Arc_Pointer;
        Arc_Pointer=new ArcNode(i,VerNode_List[j]->First_Edge,w);
        VerNode_List[j]->First_Edge=Arc_Pointer;
    }
}
void chart::Print()
{
    ArcNode*s;
    int i;
    for(i=0; i<VerNode_List.size(); i++)
    {
        //cout<<VerNode_List[i]->Vervex;
        s=VerNode_List[i]->First_Edge;
        while(s!=nullptr)
        {
            cout<<" "<<VerNode_List[i]->Vervex<<"——"<<s->Adjvex<<" ";
            s=s->next;
        }
        cout<<endl;
    }
}
chart::~chart()
{
    ArcNode*s;
    ArcNode*q;
    int i;
    for(i=0; i<VerNode_List.size(); i++)
    {
        s=VerNode_List[i]->First_Edge;
        delete VerNode_List[i];
        while(s!=nullptr)
        {
            q=s;
            s=s->next;
            delete q;
        }
    }
}
void chart::BFS(int v,int u)//说实话，这段算法其实很有局限性嗷
{
    int node=VerNode_List.size();

    //第一遍遍历时，存储各个节点到v节点的最短路径长度
    vector<int>first(node);
    //v节点到自身的距离为0
    first[v]=0;

    VerNode*t;//定点表指针
    ArcNode*tu;//边表指针
    int idx;//记录相连节点下标

    queue<VerNode*>op;
    int q_len;//队列长度

    Visited_Mark[v]=1;
    op.push(VerNode_List[v]);

    int floor=0;//记录离源点的最小层数

    while(!op.empty())
    {
        q_len=op.size();
        floor++;
        for(int i=0; i<q_len; i++)
        {
            t=op.front();
            op.pop();
            for(tu=t->First_Edge; tu!=nullptr; tu=tu->next)
            {
                idx=tu->Adjvex;
                if(Visited_Mark[idx]!=1)
                {
                    Visited_Mark[idx]=1;
                    first[idx]=floor;
                    op.push(VerNode_List[idx]);
                }
            }
        }
    }

    //第一次层序遍历没有问题
    cout<<endl<<"我先打印一下最短的路径长度："<<first[u]<<endl;


    //重置节点状态
    Reset();
    floor=0;
    //存储最短路径的数组
    vector<int>res;
    res.push_back(u);
    //再从u开始往回遍历
    Visited_Mark[u]=1;
    op.push(VerNode_List[u]);
     while(!op.empty())
    {
        q_len=op.size();
        floor++;
        for(int i=0; i<q_len; i++)
        {
            t=op.front();
            op.pop();
            for(tu=t->First_Edge; tu!=nullptr; tu=tu->next)
            {
                idx=tu->Adjvex;
                if(Visited_Mark[idx]!=1)
                {
                    Visited_Mark[idx]=1;
                    op.push(VerNode_List[idx]);
                    if((first[u]-floor)==first[idx])
                    {
                        res.push_back(idx);
                    }
                }
            }
        }
    }
    cout<<"最短路径"<<endl;
    for(int i=0;i<res.size();i++)
        cout<<res[i]<<" ";
}
void chart::Reset()
{
    int i=0;
    for(i=0; i<Visited_Mark.size(); i++)
    {
        Visited_Mark[i]=0;
        Parent[i]=-1;
        Distance[i]=INT_MAX;
    }
}
void chart::Dijkstra(int u)
{
    int node=Parent.size();//节点数
    queue<VerNode*> s;

    s.push(VerNode_List[u]);
    Parent[u]=-1;
    Distance[u]=0;

    while(!s.empty())
    {
        int idx=s.front()->Vervex;
        Visited_Mark[idx]=1;
        int last=-1;//记录最后要入队的那个节点的下标
        int last_wt=INT_MAX;
        for(ArcNode*p=VerNode_List[idx]->First_Edge;p!=nullptr;p=p->next)
        {
            int pls=p->Adjvex;
            if(Visited_Mark[pls]==0)//没有被访问过
            {
                if(((p->wet)+Distance[idx])<Distance[pls])
                {
                    Distance[pls]=((p->wet)+Distance[idx]);
                    Parent[pls]=idx;
                }
                if((p->wet)<last_wt)
                {
                    last=pls;
                    last_wt=(p->wet);
                }
            }
        }
        if(last!=-1)//如果最终选中的节点下标等于-1，那么说明没有与当前节点相连的节点了
        {
            s.push(VerNode_List[last]);
        }
        s.pop();
    }
    cout<<endl<<"当前的源节点是"<<u<<endl;
    //打印出各个数组存储的数据

    cout<<"Distance数组："<<endl;
    for(int i=0;i<node;i++)
    {
        cout<<Distance[i]<<" ";
    }
    cout<<endl<<"Parent数组："<<endl;
    for(int i=0;i<node;i++)
    {
        cout<<Parent[i]<<" ";
    }
}
void chart::Floyd()
{
    int node=Parent.size();
    //Floyd算法所需数组
    vector<vector<int>>Dist(node,vector<int>(node,INT_MAX-50));//距离数组
    vector<vector<int>>Plain(node,vector<int>(node));//顺序数组

    //初始化顺序数组
    for(int i=0; i<node; i++)
        for(int j=0; j<node; j++)
        {
            if(i==j)
            {
                Plain[i][j]=-1;
            }
            else
            {
                Plain[i][j]=j;
            }
        }

    /*先打印初始化的顺序数组*/
    cout<<"——初始化的顺序数组——"<<endl;
    for(int i=0; i<node; i++)
    {
        for(int j=0; j<node; j++)
            cout<<Plain[i][j]<<"  ";
        cout<<endl;
    }
    //初始化距离数组
    for(int i=0; i<node; i++)
    {
        int x=VerNode_List[i]->Vervex;
        for(ArcNode*p=VerNode_List[i]->First_Edge; p!=nullptr; p=p->next)
        {
            int y=p->Adjvex;
            Dist[x][y]=p->wet;
        }
    }


    //距离数组对角线
    for(int i=0; i<node; i++)
        for(int j=0; j<node; j++)
        {
            if(i==j)
                Dist[i][j]=0;
        }
    /*打印初始化的距离数组*/
    cout<<"——初始化的距离数组——"<<endl;
    for(int i=0; i<node; i++)
    {
        for(int j=0; j<node; j++)
        {
            if(i==j)
            {
                cout<<"-  ";
                continue;
            }
            if(Dist[i][j]==(INT_MAX-50))//
                cout<<"∞"<<"  ";
            else
                cout<<Dist[i][j]<<"  ";
        }
        cout<<endl;
    }

    //三层循环
    for(int k=0; k<node; k++)
    {
        for(int i=0; i<node; i++)
        {
            if(i==k)
                continue;
            for(int j=0; j<node; j++)
            {
                if(j==k)
                    continue;
                if(i==j)
                    continue;

                /*cout<<"Dist["<<i<<"]["<<k<<"]: ";
                if(Dist[i][k]==INT_MAX-50)
                    cout<<"∞"<<"  ";
                else
                    cout<<Dist[i][k]<<"  ";
                cout<<"Dist["<<k<<"]["<<j<<"]:  ";
                if(Dist[k][j]==INT_MAX-50)
                    cout<<"∞"<<"  ";
                else
                    cout<<Dist[k][j]<<"  ";
                cout<<"Dist["<<i<<"]["<<j<<"]:  ";
                if(Dist[i][j]==INT_MAX-50)
                    cout<<"∞"<<"  ";
                else
                    cout<<Dist[i][j]<<"  ";
                    cout<<endl;*/



                if((Dist[i][k]+Dist[k][j])<Dist[i][j]&&(Dist[i][k]!=(INT_MAX-50)&&Dist[k][j]!=(INT_MAX-50)))//
                {
                    Dist[i][j]=(Dist[i][k]+Dist[k][j]);
                    Plain[i][j]=Plain[i][k];
                }
            }
        }
        cout<<"——中间节点为"<<k<<"之后距离矩阵的更新——"<<endl;
        for(int i=0; i<node; i++)
        {
            for(int j=0; j<node; j++)
            {
                if(i==j)
                {
                    cout<<"-  ";
                    continue;
                }
                if(Dist[i][j]==INT_MAX-50)
                    cout<<"∞"<<"  ";
                else
                    cout<<Dist[i][j]<<"  ";
            }
            cout<<endl;
        }

    }

    //打印距离数组
    cout<<"——距离数组——"<<endl;
    for(int i=0; i<node; i++)
    {
        for(int j=0; j<node; j++)
        {
            if(i==j)
            {
                cout<<"-  ";
                continue;
            }
            if(Dist[i][j]==INT_MAX-50)
                cout<<"∞"<<"  ";
            else
                cout<<Dist[i][j]<<"  ";
        }
        cout<<endl;
    }


    //打印顺序数组
    cout<<"——顺序数组——"<<endl;
    for(int i=0; i<node; i++)
    {
        for(int j=0; j<node; j++)
            cout<<Plain[i][j]<<"  ";
        cout<<endl;
    }
}

int main()
{
    vector<int>qaq= {0,1,2,3,4};
    chart wow;
    wow.make(qaq,9);
    wow.Print();
    wow.BFS(0,4);
    wow.Reset();
    wow.Dijkstra(0);
    wow.Floyd();
    return 0;
}

运行：

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法与数据结构

算法——无向图的最短路径算法的相关文章

数组模拟环形队列(思路分析) [数据结构与算法][Java]

数组模拟环形队列思路分析使用数组模拟环形队列就可以解决使用数组模拟队列中的遗留问题了那么我们要如何使用数组模拟环形队列相当于前面讲过的数组模拟非环形队列也就是一般队列我们这里有如下的变化 front变量的含义发生了改变 fro
Leetcode_06 Z 字形变换

题目描述将一个给定字符串 s 根据给定的行数 numRows 以从上往下从左到右进行 Z 字形排列比如输入字符串为 PAYPALISHIRING 行数为 3 时排列如下 P A H N A P L S I I G Y I R 之后
[Go版]算法通关村第二关白银——两两交换链表中的节点问题解析

目录题目两两交换链表中的节点解决方法思路分析 Go代码画图说明题目两两交换链表中的节点题目链接 LeetCode 24 两两交换链表中的节点解决方法源码地址 GitHub golang版本思路分析让虚拟头结点指向链表
华为机试：最长方连续方波信号

题目来源最长方连续方波信号题目描述输入一串方波信号求取最长的完全连续交替方波信号并将其输出如果有相同长度的交替方波信号输出任一即可方波信号高位用1标识低位用0标识如图说明 1 一个完整的信号一定以0开始然后以0结尾即
二分查找的各种应用详解（C++）

基本概念 Binary Search 二分查找也称折半查找它是一种效率较高的查找方法使用二分查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列基本原理查找因为序列已经单调且有序排列从中间位置开始比较一次可以排除一
算法基础——大O表示法

本期主题算法的大O表示法目录 1 什么是大O表示法 2 时间复杂度 2 1 时间复杂度定义 2 2 常见算法的时间复杂度 3 数组与链表对比 1 什么是大O表示法大O表示法是一种特殊的表示方式指出了算法的速度指出了最糟情况下的运行
顺序查找算法C语言实现

顺序查找算法实现思想静态查找表用顺序存储结构表示时顺序查找的查找过程为从表中的最后一个数据元素开始逐个同记录的关键字做比较如果匹配成功则查找成功反之如果直到表中第一个关键字查找完也没有成功匹配则查找失败应用场景顺序查
动态规划：国王与金矿

题目解析有一个国家发现了5座金矿每座金矿的黄金储量不同需要参与挖掘的工人数也不同参与挖矿工人的总数是10人每座金矿要么全挖要么不挖不能派出一半人挖取一半金矿要求用程序求解出要想得到尽可能多的黄金应该选择挖取哪几座金矿第
【Leetcode】61. 旋转链表

题目描述给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置题解旋转链表找倒数第k个节点翻转前后链表执行用时 0 ms 在所有 Java 提交中击败了100 00 的用户内存消耗 37 8 MB 在所有
【Leetcode】560. 和为K的子数组

题目描述给你一个整数数组 nums 和一个整数 k 请你统计并返回该数组中和为 k 的连续子数组的个数题解暴力解法双循环 i指针从左往右走 j指针从i往左走一个个遍历一个个加起来直到加到等于k 就计数一次执行用时 1445 m
【C++后台开发面试】STL相关

此部分较为精简只供面试前联想记忆使用需要先熟读相关的内容知识才能发挥其作用推荐书籍 STL源码剖析侯捷六大组件及其关系空间配置器容器迭代器算法仿函数适配器内存管理内存配置和对象构造析构分开使用双层级配置器第一
力扣刷题-210.课程表Ⅱ、图的表示方式、BFS

一图的基本概念定义和基本术语图是由节点以及连接这些节点边组成无向图每条边连接的两个节点可以双向访问有向图每条边连接的两个节点只能单向访问出度有向图的某个节点作为起点的次数和入度有向图的某个节点作为终点的次数和权重图
算法训练营day48

文章目录 198 打家劫舍思路分析代码实现思考总结 213 打家劫舍II 思路分析代码实现 337 打家劫舍 III 树形DP 思路分析代码实现思考总结 198 打家劫舍题目链接你是一个专业的小偷计划偷窃沿街的房屋每间房
Java中Arrays类的常用方法

Java中Arrays类的常用方法 Arrays类位于 java util 包中主要包含了操作数组的各种方法 import java util Arrays Arrays fill 填充数组 int arr new int 5 新建一个大
LeetCode-剑指 Offer II 114. 外星文字典，BFS 搜索算法及图的表示

剑指 Offer II 114 外星文字典现有一种使用英语字母的外星文语言这门语言的字母顺序与英语顺序不同给定一个字符串列表 words 作为这门语言的词典 words 中的字符串已经按这门新语言的字母顺序进行了排序请你根据该词典
为什么说快速排序是性能最好的排序算法？

刚刚学习了排序这一章看到了书中最后的一个总结表心想从表上来看堆排序不该是最好的排序算法么不管最好最坏还是平均情况时间复杂度都是O nlogn 而且还不像快排和归并排序那样占空间为什么说快速排序是最好的算法呢其实经过实验会发
二叉查找树(BST)的基本概念及常用操作

二叉查找树二叉查找树 Binary Search Tree 也称二叉搜索树有序二叉树 ordered binary tree 排序二叉树 orted binary tree 是指一棵空树或者具有下列性质的二叉树若任意节点的左子树不空
数据结构系列——链表linklist

本期主题数据结构之链表往期链接数据结构系列先进先出队列queue 数据结构系列栈 stack 目录 1 链表定义 2 代码实现链表 1 链表定义定义链表由多个结点组成结点不仅包含值还包含到下一个结点的信息所以通过这种方
图解 Dijkstra、Floyd、BellMan-Ford 最短路径算法

文章目录导言一迪杰斯特拉算法 Dijkstra 1 概述 2 算法描述 3 图片解释 4 Dijkstra算法实现 5 Dijkstra Heap算法实现二弗洛伊德算法 Floyd Warshall 1 概述 2 算法描述 3 算
哈希表设计思想及实现

哈希表设计思想及实现定义哈希表在算法4 这本书中是这么介绍的哈希表其实又叫散列表是算法在时间和空间上做出权衡的经典例子如果一个表所有的键都是小整数我们就可以用一个数组来实现无序的符号表将键作为数组的索引而数组中i出存储的值就

随机推荐

-bash: nginx: command not found 解决方案

楼主已经安装了Nginx在Linux下面然后也把Nginx启动了此时想重新加载一下Nginx 然后输入命令居然发生了下面的错误我的Linux系统是 centos 6 5 的 root zxc sbin nginx s reload
vue-axios的总结及项目中的常见封装方法。

前言我们知道 vue 2 0版本开始推荐使用 axios 来完成前端 ajax 请求 axios 是一个基于Promise 的 http 库可以用在浏览器和 node js 中 axios 成为vue全家桶的一个重要部分对前后端接口请
Unity 四元数、欧拉角、轴角之间的互相转换

using UnityEngine public class RotateTest MonoBehaviour public Transform a public Transform b public Transform c void St
springboot整合微信扫码支付(详细)

微信扫码支付以下主要是针对微信支付V3接口进行的整合且为Native支付前期准备工作 1 获取微信相关数据绑定支付的appid 商户id 商户支付秘钥wechatKey 这个需要V3的证书序列号私钥文件 pem文件下面给出了相
Boost电压闭环控制及其仿真（PI控制）

这是自己本科做的一项综合设计作业自动控制理论的课程作业题目是 DC DC升压变换单电压环控制器设计我查了不少资料硕士论文文献等断断续续地花了1个半月解决的当时老师手中有两个作业一个是Boost单电压闭环控制仿真另外一个是B
llama2模型下载

介绍 LLaMA 2 CHAT与OpenAI ChatGPT效果一样好 LLaMA 2与LLaMA 1架构相同 LLaMA 2训练数据是2000000000000个tokens 还是用了1000000个人类新标注的数据上下文长度由2048
前端实战复习——歌词滚动

歌词滚动此处展示为html的demo 思路首先歌词单独为div 歌词整体滚动设置wrap为div 歌词上移使用移动wrap位置所以需要设置wrap position为absolute 歌词高亮使用当前歌词改变类名实现添加过渡tra
C++ CopyFile函数的用法

CopyFile函数定义在Windows h中使用时要include之 CopyFile 使用如下 include
一篇文章彻底学会递归思路解题

一篇文章彻底学会递归思路解题前言递归是算法中一种非常重要的思想应用也很广小到阶乘再在工作中用到的比如统计文件夹大小大到 Google 的 PageRank 算法都能看到也是面试官很喜欢的考点最近看了不少递归的文章收获不小
blender硬表面建模渲染终极教程

blender硬表面建模渲染终极教程 Gumroad The ULTIMATE Guide to Hard Ops and Boxcutter Gumroad 硬操作和切箱机的终极指南教程大小 6G 1920X1080分辨率语言英语
7-12 最长对称子串（25 分)

对给定的字符串本题要求你输出最长对称子串的长度例如给定Is PAT TAP symmetric 最长对称子串为s PAT TAP s 于是你应该输出11 输入格式输入在一行中给出长度不超过1000的非空字符串输出格式在一行中输出
Elasticsearch 笔记

文章目录 Elasticsearch 快速安装安装启动问题踩坑状态验证 Elasticsearch 基础使用查看节点列表列出索引信息查看节点分片信息其他的一些信息查询创建索引索引和查询文档删除索引修改数据探索数据搜
基于SSM的智慧城市实验室主页系统的设计与实现

末尾获取源码开发语言 Java Java开发工具 JDK1 8 后端框架 SSM 前端采用Vue技术开发数据库 MySQL5 7和Navicat管理工具结合服务器 Tomcat8 5 开发软件 IDEA Eclipse 是否Mave
Python 最常用模块函数代码汇总解析

一文件和目录操作创建删除修改拼接获取当前目录遍历目录下的文件获取文件大小修改日期判断文件是否存在等二日期和时间内置模块 time datatime calendar 1 time time 返回自1970年1月1日
Go换国内源解决go get -u 问题

Go版本1 13及以上 Windows在编译器终端执行以下操作 go env w GO111MODULE on go env w GOPROXY https goproxy cn direct MacOS或Linux export GO11
java 可变参数详解（通俗易懂）

目录一概述二格式三注意事项使用规范四代码演示演示规范演示规范演示规范课堂练习代码演示输出结果五英文版本讲解一概述 java中我们可以将名称相同功能也相同但是形参个数不同的多个函数封装为某个类中的
avue form弹框里改动label

可参考官网弹窗表单配置 Avue
springboot 配置logback

logback spring xml文件配置
Oracle数据库报错ERROR at line 1:ORA-01157: cannot identify/lock data file 9

自说今天在打开了好久没有打开的rac数据库时重启数据库进入open模式时发生了以下错误经过简单筛查后发现是因为之前创建的数据文件删除掉了因为我这里是保存到了本地中 E盘下未找到导致报错我们可以查看 set linesize 19
算法——无向图的最短路径算法

https www jb51 net article 154796 htm 我是看上面的文章写的程序他的第一种解法还需要我再理解理解 BFS一层层寻找目标节点的算法思路 1 先从v到u的使用BFS遍历一遍图得到每个节点到v的最短距离

算法——无向图的最短路径算法

算法——无向图的最短路径算法 的相关文章

随机推荐

热门标签

算法——无向图的最短路径算法的相关文章