本文介绍: 计算机网络传输问题怎样找到一种最经济的方式,从一台计算机网上所有其他计算机发送一条消息抽象为:给定带权有向图G=(V,E)和源点v,求从v到G中其余各顶点的最短路径给定带权有向图G=(V,E)和源点vV,求从v到G中其余各顶点的最短路径

一.引例

计算机网络传输问题

怎样找到一种最经济的方式,从一台计算机网上所有其他计算机发送一条消息。

抽象为:

给定带权有向图G=(V,E)和源点v,求从v到G中其余各顶点的最短路径

即:

单源点最短路径问题

给定带权有向图G=(V,E)和源点v$in$V,求从v到G中其余各顶点的最短路径

二.最短路径

在非网图中,最短路径是指两顶点之间经历的边数最少的路径。

在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径。

三.Dijskra算法基本思想

        设置一个集合S存放已经找到最短路径的顶点,S的初始状态包含源点v,对vi属于V-S,假设从原点v到vi的有向边为最短路径。以后每求得一条最短路径v,……,vk,就将vk加入集合S中,并将路径v,……,vkvi与原来的假设比较,取路径长度较小者为最短路径。重复上述过程,直到集合V中全部顶点加入集合S中。

四.Dijskra算法数据结构

1.图的存储结构

带权邻接矩阵存储结构(因为需要频繁的读取边)

2.数组dist[n]:

每个分量dist[i]表示当前找到的从起始点v到终点vi的最短路径的长度

初态为:若从v到vi有弧,则dist[i]为弧上权值;否则置dist[i]为$infty$

3.数组path[n]:

path数组下标为图每个顶点的编号数组中的元素为由某个顶点到这个顶点的顶点编号

初态为:若从v到vi有弧,则path[i]为0;否则path[i]为-1。

最终输出最短路径,依靠path数组

每次更改dist数组的内容,都会在path数组中更新上一个结点内容

4.数组s[n]:

存放源点和已生成的终点,其初态为只有一个源点v。

s数组都初始化为0(源点初始化为1),当该点被放入s集合中,将其置为1。

 五.伪代码

1.初始化数组distpaths

2.whiles中的元素个数<n

        2.1 在dist[n]中求最小值,其下标k

        2.2 输出dist[i]和path[j];

        2.3 修改数组distpath

        2.4 将顶点vk添加到数组s

六.代码实现 

#include <iostream>

using namespace std;

const int MAX_VERTEX=10;

//带权邻接矩阵有向图
class MGraph{
private:
    int arc[MAX_VERTEX][MAX_VERTEX];//邻接矩阵
    int vertex[MAX_VERTEX];//存储每个结点信息
    int vertexNum,arcNum;//实际顶点个数,边的条数
public:
    MGraph(int n,int e);
    void Dijkstra(int start);
    int findMinDist(int dist[],int s[]);
    void display();
    void displayPath(int dist[],int path[],int start,int min);
};

int main(int argc, const char * argv[]) {
    MGraph G(5, 7);
    //G.display();
    G.Dijkstra(0);
    return 0;
}
MGraph::MGraph(int n,int e){
    int p,q,w;
    vertexNum=n;
    arcNum=e;
    for(int i=0;i<n;i++){//初始化邻接矩阵
        for(int j=0;j<n;j++){
            arc[i][j]=-1;//-1表示不可到达
        }
    }
    for(int i=0;i<n;i++){
        vertex[i]=i;
        arc[i][i]=0;
    }
    for(int i=0;i<e;i++){
        cin&gt;&gt;p&gt;&gt;q&gt;&gt;w;
        arc[p][q]=w;
    }
}

void MGraph::Dijkstra(int start){
    int *s=new int[vertexNum];
    int *dist=new int[vertexNum];
    int *path=new int[vertexNum];
    int i,num=0,min;
    for(i=0;i<vertexNum;i++){
        dist[i]=arc[start][i];//初始化距离
        s[i]=0;//初始化集合S
        if(arc[start][i]!=-1){//start到i有路径
            path[i]=start;
        }
        else{
            path[i]=-1;
        }
    }
    s[start]=1;//将源点放入集合S中,1表示在集合中,0表示不在集合num++;//num记录集合S中元素的个数
//    for(int i=0;i<vertexNum;i++){
//        cout<<dist[i]<<" ";
//    }
//    cout<<endl;
    while(num<vertexNum){
        min=findMinDist(dist, s);//dist中查找集合S中不存在的顶点到源点的距离最小值
        cout<<min<<endl;
        s[min]=1;//将新生成的终点加入到集合S中
        num++;
        for(i=0;i<vertexNum;i++){//更新数组dist和path
            if(s[i]==0&amp;&amp;arc[min][i]!=-1){
                if(dist[i]==-1){
                    dist[i]=dist[min]+arc[min][i];//更新dist数组
                    path[i]=min;//更新path数组
                }
                else if(dist[i]!=-1&amp;&amp;(dist[min]+arc[min][i])<dist[i]){
                    dist[i]=dist[min]+arc[min][i];
                    path[i]=min;//更新path数组
                }
            }
        }
//        for(int i=0;i<vertexNum;i++){
//            cout<<dist[i]<<" ";
//        }
//        cout<<endl;
        displayPath(dist, path, start, min);
    }
    delete [] path;
    delete [] s;
    delete [] dist;
}

int MGraph::findMinDist(int dist[],int s[]){
    int i=0,min=0;
    for(i=0;i<vertexNum;i++){//给min赋初始值
        if(s[i]==0&amp;&amp;dist[i]!=-1){//该顶点不在集合S中
            min=i;
            break;
        }
    }
    for(;i<vertexNum;i++){
        if(s[i]==0){//该顶点不在集合S中
            if(dist[i]!=-1&amp;&amp;dist[min]>dist[i]){
                min=i;
            }
        }
    }
    return min;
}

void MGraph::displayPath(int dist[],int path[],int start,int min){
    int pre=min;
    int p[vertexNum],i=0,j;
    while(pre!=start){
        p[i++]=pre;
        pre=path[pre];
    }
    p[i++]=pre;
    cout<<"(";
    for(j=i-1;j>0;j--){
        cout<<p[j]<<",";
    }
    cout<<p[0]<<")";
    cout<<dist[min]<<endl;
}
void MGraph::display(){
    for(int i=0;i<vertexNum;i++){
        for(int j=0;j<vertexNum;j++){
            cout<<arc[i][j]<<" ";
        }
        cout<<endl;
    }
}

 

原文地址:https://blog.csdn.net/Hsianus/article/details/134539413

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_49024.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注