精华内容
下载资源
问答
  • 单源最短路径问题: 无权 从某一固定点到其他所有点的最短路径 首先用dist[ w ] = v;记录距离,意义为点 v 到 点 w 的距离,v 为起始点, w 为终点; 然后用path[ w ] = v;记录点的关系,v 为起始点, w...

    单源最短路径问题:(参考中国MOOC内容和百度百科较大部分,因本想转载,发现没有转载网址,所以归为原创,若有侵权,请联系删除)

    1. 无权图
      从某一固定点到其他所有点的最短路径
    2. 首先用dist[ w ] = v;记录距离,意义为点 v 到 点 w 的距离,v 为起始点, w 为终点;
    3. 然后用path[ w ] = v;记录点的关系,v 为起始点, w 为终点;
      最开始赋初值dist[ i ] = -1和 path[ i ] = -1都赋值为-1;
      但是原点的距离即 dist[ 0 ] = 0;
      可以按照距离的递增或递减顺序找出最短路:
      在这里插入图片描述
      很类似广度优先搜索算法,在此基础上进行改动,的得到:
      数组:
    int map[Maxsize][Maxsize];//关系图
    int Queue[Maxsize];
    int front = -1;
    int rear = -1;
    void Unweighted(int top,int N,int dist[],int path[])
    {
    	int v = 0,i = 0;
    	Queue[++rear] = top;
    	while(front != rear)
    	{
    		v = Queue[++front];
    		for(i = 1;i <= N;i++)
    		{
    			if(dist[i] == -1 && map[v][i]) //表示没有访问
    			{
    				dist[i] = dist[v] + 1;
    				path[i] = v;
    				Queue[++rear] = i;  //入队
    			}
    		}
    	}
    }
    int main()
    {
    	int N,i = 0,dist[Maxsize],path[Maxsize],yuandian = -1;
    	scanf("%d",&N);//顶点数
    	for(i = 1;i <= N ;i++)//初始化
    	{
    		scanf("%d %d",&v,&w);
    		map[v][w] = 1;//表示连接关系,无向图
    		map[w][v] = 1;
    		dist[i] = -1;
    		path[i] = -1;
    	}
    	scanf("%d",&yuandian); //起点
    	dist[yuandian] = 0;
    	Unweighted(yuandian,N,dist,path);
    }

    链表

    void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
    {
        Queue Q;
        Vertex V;
        PtrToAdjVNode W;
        Q = CreateQueue( Graph->Nv );
        dist[S] = 0;
        AddQ (Q, S);
        while( !IsEmpty(Q) ) 
       {
            V = DeleteQ(Q);
            for ( W = Graph->G[V].FirstEdge; W; W = W->Next )
                if ( dist[W->AdjV] == -1 )
      	    {
                    dist[W->AdjV] = dist[V]+1;
                    path[W->AdjV] = V;
                    AddQ(Q, W->AdjV);
                 }
        }
    }
    1. 有权图
      类似题目点击了解
      数组
    void Dijkstra(int top)
    {
    	while( 1 )
    	{
    		int temp = -1;
    		for(i = 0; i <= N - 1;i++)    //未收录的顶点中的dist[ i ]最小值
    		{
    			if(collected[i] == 0)
    			{
    				 if(temp > dist[i])
    				 	temp = diat[i];
    			}
    		}
    		if(temp == -1)//如果不存在这样的点
    			break;
    		collected[ v ] = 1;//收录进去
    		for(i = 0;i <= N - 1;i++)
    		{
    			if(collected[i] = 0) //表示没有访问
    			{
    				if(dist[w] > dist[w] + dist<v,w>)
    				{
    					dist[w] = dist[v] + dist<v,w>;
    					path[w] = v;
    		   		 }
    		 	}
    		}
     	}
    return ;
    }

    链表

    Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
    {
        Vertex MinV, V;
        int MinDist = INFINITY;
        for (V = 0; V <= Graph->Nv - 1; V++)
        {
            if ( collected[V]==false && dist[V]<MinDist)
            {
                MinDist = dist[V]; // 更新最小距离
                MinV = V;//更新对应顶点
            }
        }
        if (MinDist < INFINITY) //存在
            return MinV;
        else return 0;//不存在
    }
    int Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
    {
        int collected[MaxVertexNum];
        Vertex V, W;
        for ( V = 0; V <= Graph->Nv - 1; V++ ) //接矩阵中不存在的边用INFINITY表示
        {
            dist[V] = Graph->G[S][V];
            if ( dist[V]<INFINITY )
                path[V] = S;
            else
                path[V] = -1;
            collected[V] = 0;
        }
        dist[S] = 0;//起点自身距离为零
        collected[S] = 1;//起点收入集合
        while (1)
        {
            V = FindMinDist( Graph, dist, collected );
            if ( V == 0 ) // 若这样的V不存在
                break;
            collected[V] = true;  // 收录v
            for( W = 0; W <= Graph->Nv - 1; W++ )
            {
                if ( collected[ W ] == false && Graph->G[V][W] < INFINITY )
      	    {
                    if ( Graph->G[V][W] < 0 ) // 若有负边
                        return 0;
                    if ( dist[V] + Graph->G[V][W] < dist[W] ) 
                    {
                        dist[W] = dist[V] + Graph->G[V][W];
                        path[W] = V; // 更新S到W的路径
                    }
                }
    	}
        }
        return 1;
    }

    多源最短算法
    邻接矩阵存储(Floyd算法,弗洛伊德算法)(此分析转自百度百科
    5. 从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
    6. 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它.
    7. 把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[ i ][ j ]=d,d表示该路的长度;否则G[ i ][ j ]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[ i ][ j ]表示从Vi到Vj需要经过的点,初始化D[ i ][ j ]=j。
    8. 把各个顶点插入图中,比较插点后的距离与原来的距离,G[ i ][ j ] = min( G[ i ][ j ], G[ i ][ k ]+G[ k ][ j ] ),如果G[ i ][ j ]的值变小,则D[ i ][ j ] = k。
    9. 在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。
    优缺点分析:
    Floyd算法适用于APSP(All Pairs Shortest Paths,多源最短路径),是一种动态规划算法,稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法,也要高于执行|V|次SPFA算法。
    优点:容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。
    缺点:时间复杂度比较高,不适合计算大量数据。

    int Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
    {
        Vertex i, j, k;
        for ( i = 0; i < Graph->Nv; i++ )
        {
            for( j = 0; j < Graph->Nv; j++ )
     	{
                D[i][j] = Graph->G[i][j];
                path[i][j] = -1;
            }
        }
        for( k = 0; k < Graph->Nv; k++ )
            for( i = 0; i < Graph->Nv; i++ )
                for( j = 0; j < Graph->Nv; j++ )
                    if( D[i][k] + D[k][j] < D[i][j] ) 
                    {
                        D[i][j] = D[i][k] + D[k][j];
                        if ( i == j && D[i][j]<0 ) // 若发现负值圈
                            return 0;
                        path[i][j] = k;
                    }
        return 1;
    }
    展开全文
  • 单源/多源最短路径

    2020-04-03 16:23:20
    单源最短路径 单元无权最短路径 int dist[MAX_VERTEX]; int path[MAX_VERTEX]; void unWeightedSP(int v) { for (int i = 0; i < nv; ++i) { dist[i] = -1; } dist[v] = 0; queue<int> q; q.push(v...

    单源最短路径

    • 单源即一个起点,指从图中某个结点开始到其他所有结点

    单源无权最短路径

    关于本例中图的邻接矩阵创建参见 图的深搜和广搜

    int dist[MAX_VERTEX];
    int path[MAX_VERTEX];
    
    void unWeightedSP(int v)
    {
    	for (int i = 0; i < nv; ++i) {
    		dist[i] = -1;
    	}
    	dist[v] = 0;
    	queue<int> q;
    	q.push(v);
    	while (!q.empty()) {
    		int u = q.front();
    		q.pop();
    		for (int j = 0; j < nv; ++j) {
    			if (MGraph[u][j] == 1&& dist[j] == -1) {
    				dist[j] = dist[u] + 1;
    				path[j] = u;
    				q.push(j);
    			}
    		}
    	}
    }
    

    有权图的单源最短路算法 Dijstra

    Dijkstra算法
    在这里插入图片描述

    void Dijsktra(int v)
    {
    	int i;
    	//初始化
    	for (i = 0; i < nv; ++i) {
    		dist[i] = 9999;
    		path[i] = -1;
    	}
    	dist[v] = 0;
    
    	while (1) {
    		//获取未收录结点中距离源点距离最小者
    		int u = getMinDistV();
    		if (u == -1)break;//循环退出条件
    		collected[u] = 1;
    		//依次遍历u的邻接点
    		for (int j = 0; j < nv; ++j) {
    			if ((MGraph[u][j] > 0) && (collected[j] == 0)) {
    				if (dist[u] + MGraph[u][j] < dist[j]) {
    					dist[j] = dist[u] + MGraph[u][j];
    					path[j] = u;
    				}
    			}
    		}
    	}
    }
    int getMinDistV()
    {
    	int i;
    	int minDist = 9999;
    	int minV = -1;
    	for (i = 0; i < nv; ++i) {
    		if ((minDist > dist[i])&&(collected[i]==0)) {
    			minDist = dist[i];
    			minV = i;
    		}
    	}
    	return minV;
    }
    
    • Full Code

      #include<iostream>
      #include<queue>
      
      using namespace std;
      
      #define MAX_VERTEX 100
      
      int MGraph[MAX_VERTEX][MAX_VERTEX];
      int visit[MAX_VERTEX];
      
      int nv, ne;
      void creatMGraph();
      void printMGraph();
      void Dijsktra(int v);
      int getMinDistV();
      int dist[MAX_VERTEX];
      int collected[MAX_VERTEX];
      int path[MAX_VERTEX];
      
      int main()
      {	
      	creatMGraph();
      	printMGraph();
      	Dijsktra(0);
      	for (int i = 0; i < nv; ++i)cout << dist[i] << " ";
      	system("pause");
      	return 0;
      }
      void creatMGraph()
      {
      	cout << "请输入结点数nv: ";
      	cin >> nv;
      	//初始化
      	int i, j;
      	for (i = 0; i < nv; ++i) {
      		visit[i] = 0;	
      	}
      	for (i = 0; i < nv; ++i) {
      		for (j = 0; j < nv; ++j) {
      			MGraph[i][j] = 0;
      		}
      	}
      	//添加边
      	cout << "请输入边数ne:";
      	cin >> ne;
      	cout << "请依次输入边及权重(例如:3 1 2): " << endl;
      	int w;
      	for (int k = 0; k < ne; ++k) {
      		cin >> i >> j >> w;
      		MGraph[i][j] = w;
      	}
      }
      void printMGraph()
      {
      	int i, j;
      	for (i = 0; i < nv; ++i) {
      		for (j = 0; j < nv; ++j) {
      			cout << MGraph[i][j] << " ";
      		}
      		cout << endl;
      	}
      }
      void Dijsktra(int v)
      {
      	int i;
      	//初始化
      	for (i = 0; i < nv; ++i) {
      		dist[i] = 9999;
      		path[i] = -1;
      	}
      	dist[v] = 0;
      
      	while (1) {
      		//获取未收录结点中距离源点距离最小者
      		int u = getMinDistV();
      		if (u == -1)break;//循环退出条件
      		collected[u] = 1;
      		//依次遍历u的邻接点
      		for (int j = 0; j < nv; ++j) {
      			if ((MGraph[u][j] > 0) && (collected[j] == 0)) {
      				if (dist[u] + MGraph[u][j] < dist[j]) {
      					dist[j] = dist[u] + MGraph[u][j];
      					path[j] = u;
      				}
      			}
      		}
      	}
      }
      int getMinDistV()
      {
      	int i;
      	int minDist = 9999;
      	int minV = -1;
      	for (i = 0; i < nv; ++i) {
      		if ((minDist > dist[i])&&(collected[i]==0)) {
      			minDist = dist[i];
      			minV = i;
      		}
      	}
      	return minV;
      }
      

    多源最短路径 Floyd

    • 多源即图中任意两个结点
      在这里插入图片描述
    void Floyd()
    {
    	int i, j, k;
    	for (i = 0; i < nv; ++i) {
    		for (j = 0; j < nv; ++j) {
    			Dist[i][j] = MGraph[i][j] > 0 ? MGraph[i][j] : 9999;
    			Path[i][j] = -1;
    		}
    	}
    	for (k = 0; k < nv; ++k) {
    		for (i = 0; i < nv; ++i) {
    			for (j = 0; j < nv; ++j) {
    				if (Dist[i][k] + Dist[k][j] < Dist[i][j]) {
    					Dist[i][j] = Dist[i][k] + Dist[k][j];
    					Path[i][j] = k;
    				}
    			}
    		}
    	}
    }
    
    
    展开全文
  • 直流微电网系统设计将包括 2 个 50W 光伏阵列作为电源连接到各自的太阳能充电控制器,该控制器使用脉宽调制控制降压转换器,同时提供一个 3 点电网,每个点都有一个直流负载,这些负载是可变负载是定制设计的带...
  • –在网络中,求两个不同顶点之间的所有路径中,边的权值之最小的路劲。 单源最短路径 –从某固定源点出发的最短路径 无权的最短路径 按照路径长度递增的顺序找出源点到各个顶点的最短路径 类似于BFS-宽度...

    最短路径

    –在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的路劲。

    单源最短路径

    –从某固定源点出发的最短路径

    无权图的最短路径
    • 按照路径长度递增的顺序找出源点到各个顶点的最短路径

    在这里插入图片描述

    • 类似于BFS-宽度优先遍历,可以通过队列来实现,

      • 先让顶点入队,循环执行下列步骤
      • 出队首元素,访问其所有邻接点
      • 标明源点到这些邻接点的路径长度,并将其入队
    有权图的最短路径
    Dijkstra算法
    • 令第一组为集合S={源点+已经确定最短路径的顶点vi}

    • 令第二组为未在集合S中的顶点v,定义length成员为源点s到v的最短路径长度,该路径除了终点v以外,所有顶点都必须是集合S中的顶点。即{s—>(vi∈S)—>v}的最小长度

    • 每次对未在第一组集合S的顶点,选一个length最小的顶点(记为v),将其增加至集合S中。

      • 如何选这个顶点V–用一个最小堆H(刚开始只有源点),每次找出并删除一个length值最小的顶点V,这里这个找到并删除的顶点V就是每次加入集合S的顶点,然后找到V的所有邻接点,对其邻接点的length值进行赋值,然后加入最小堆H里,往复循环,直至最小堆空了(最小堆空了,即所有顶点都加入了集合S)–看程序就明白了

      • 选进去的时候要注意什么–增加v进集合S中会影响顶点w(w为v的邻接点)的length值,因为多了个顶点v,可能会改变s—w的走法,原先不经过v,现在最短路径经过v,即需要考虑

        length[w],与length[v] + e.weigth的大小关系--------(1)

    • 直到把所有顶点都送进集合S中

    在这里插入图片描述

    设源点为V0,则按照Dijkstra算法的最短路径求解过程如下

    在这里插入图片描述

    注:初始的时候只有集合S只有源点s,因此只有到点v1、v2有路径,路径长度用length表示,,没有路径则length为∞,路径的终点的前一个点用pre表示。

    ```C++
    class Dist { // Dist类,用于保存最短路径信息
     public:
      int index; // 结点的索引值
      int length; // 当前最短路径长度
      int pre; // 路径最后经过的结点
    };
    
    void Dijkstra(Graph& G, int s, Dist* &D) { // s是源点
     D = new Dist[G. VerticesNum()]; // 开辟空间给类Dist,用来记录当前最短路径长度
        
    
        
     for (int i = 0; i < G.VerticesNum(); i++) { // 初始化,将图中所有顶点的标志位记为未访问,将Dist类的索引值记为顶点号,将顶点到源点的length置为∞。
         G.Mark[i] = UNVISITED; 
         D[i].index = i; 
         D[i].length = INFINITE;
         D[i].pre = s;
       }
        D[s].length = 0; // 初始化,源点自身的路径长度置为0
        
        
     MinHeap<Dist> H(G. EdgesNum()); // 最小堆用于找出集合S中到源点的路径最短的点,最小堆存放Dist类元素,共有G.EdgesNum个长度
     H.Insert(D[s]);  //将源点放入最小堆
        
        
     
     for (i = 0; i < G.VerticesNum(); i++) {
       bool FOUND = false;
       Dist d;
       while (!H.isEmpty()) {
         d = H.RemoveMin(); //获得集合S中到源点s路径长度最小的结点,并删除
         if (G.Mark[d.index] == UNVISITED) { //如果未访问过则跳出循环
            FOUND = true; break;
         } 
        }
        if (!FOUND) break; // 若没有符合条件的最短路径则跳出本次循环
        int v = d.index; 
        G.Mark[v] = VISITED; // 将标记位设置为 VISITED
        for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) // 对最小堆中到源点路径最短的顶点v,求他的每个邻接点,并考虑是否需要改变其最小距离--刷新最短路,然后将其加入最小堆
          if (D[G.ToVertex(e)].length > (D[v].length+G.Weight(e))) {//这里第一次执行时,因为刚开始最小堆里只有源点,其他顶点到源点的length都为∞,执行完后V1、V2的length值才改变
            D[G.ToVertex(e)].length = D[v].length + G.Weight(e);
            D[G.ToVertex(e)].pre = v;
            H.Insert(D[G.ToVertex(e)]);
        } 
     }
    } 
    
    
    

    Dijkstra算法时间复杂度

    T = O ( ∣ V ∣ l o g ∣ V ∣ + ∣ E ∣ l o g ∣ V ∣ ) = O ( ∣ E ∣ l o g ∣ V ∣ ) T = O( |V| log|V| + |E| log|V| ) = O( |E| log|V| ) T=O(VlogV+ElogV)=O(ElogV)

    前半部分为在最小堆里找V次,依次复杂度为logV,后半部分是往最小堆里插入Dist,一次最多有可能插E次(极限情况,一个顶点有E条边)

    Dijkstra使用条件
    • 图中不能出现有总权值为负值的回路
    • 如果存在负值边也有可能发生计算错误
    • 持负权值的最短路径算法有Ford算法、SPFA算法

    多源最短路径

    –求每对顶点间的最短路径

    Floyd算法
    • Dk[i] [j]表示路径{ i —> { l<= k } —> j }的最小长度(i、j、l、k表示顶点编号)

    • 首先用矩阵D0表示该图的邻接矩阵

    • 在矩阵D0上做n次迭代

    • 如何迭代呢–当Dk-1已经完成,递推到Dk时,

      • 若k∉最短路径{ i —> { l<= k } —> j },(即i到j的最短路径不经过k)则Dk=Dk-1

      • 若k∈最短路径{ i —> { l<= k } —> j }(即i到j的最短路径经过k),则该最短路径由两条路径组成:
        D ( k ) [ i ] [ j ] = D ( k − 1 ) [ i ] [ k ] + D ( k − 1 ) [ k ] [ j ] D(k)[i][j]=D(k-1)[i][k]+D(k-1)[k][j] D(k)[i][j]=D(k1)[i][k]+D(k1)[k][j]

    cpp
    void Floyd(Graph& G, Dist** &D) {
        int i,j,v;
        D = new Dist*[G.VerticesNum()]; // 申请空间,申请一个与邻接矩阵等大的D
        for (i = 0; i < G.VerticesNum(); i++)
          D[i] = new Dist[G.VerticesNum()];
          
          // 初始化数组D
        for (i = 0; i < G.VerticesNum(); i++) 
         for (j = 0; j < G.VerticesNum(); j++) {
          if (i == j) { 
              D[i][j].length = 0;
              D[i][j].pre = i; }
          else { 
              D[i][j].length = INFINITE; 
              D[i][j].pre = -1; 
          } 
         }
        //对D0矩阵进行赋值,让其与邻接矩阵相同
       for (v = 0; v < G.VerticesNum(); v++)
        for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) {
            D[v][G.ToVertex(e)].length = G.Weight(e);
            D[v][G.ToVertex(e)].pre = v; }
       
          
          
          // 加入新结点后,更新那些变短的路径长度
        for (k = 0; k< G.VerticesNum(); k++)
         for (i = 0; i < G.VerticesNum(); i++)
          for (j = 0; j < G.VerticesNum(); j++)
              
           if (D[i][j].length > (D[i][k].length+D[k][j].length)) {
               D[i][j].length = D[i][k].length+D[k][j].length; 
               D[i][j].pre = D[k][j].pre;//第k次迭代,考虑在加入编号为k的顶点的情况下,是否需要更新i、j之间的路径长度
           } 
      }
      
    
    Floyd算法时间复杂度

    T = O ( ∣ V ∣ 3 ) T = O( |V|3 ) T=O(V3)

    展开全文
  • #include<bits/stdc++.h> using namespace std; int dist[1000]={0};//从原点到当前节点的最短路 int path[1000]={0};...// int vis[1000]={0}; int m,n; /* 7 12 1 2 2 1 4 1 2 4 3 ...

    无权图的单源最短路:

    void Unweighted( Vertex s){
        queue<Vertex> q;
        q.push(s);
        wile(!q.empty()){
            v = q.front(); q.pop();
            for( V 的每个临界点 W){
                dist[W] = dist[v] + 1; // 当前距离上一距离 + 1
                path[W] = v;  // s 到 w 的必经顶点就是前一个顶点 v
                q.push(W);
            }
        }
    }
    
    

    有权图的单源最短路

    void Dijkstra( Vertex s ){
        while(1){
            V = 未收录顶点中dist最小值;
            if( 这样的V不存在 )
                break;
            collected[V] = true;
            for( V 的每个邻接点 W )
                if( collected[W] == false )
                    if(dist[V] + E<V,W> < dist[W]){
                 		dist[W] = dist[V] + E<V,W>;
                        path[W] = V;
                    }
        }
    }
    
    
    

    列子:

    #include<bits/stdc++.h>
    using namespace std;
    int dist[1000]={0};//从原点到当前节点的最短路 
    int path[1000]={0};//当前节点的前一个节点 
    int G[1000][1000]={0};//图 
    int vis[1000]={0};
    int m,n;
    /*
    7
    12
    1 2 2
    1 4 1
    2 4 3
    2 5 10
    3 1 4
    3 6 5
    4 3 2
    4 6 8
    4 7 4
    4 5 2
    5 7 6
    7 6 1
    */ 
    void build(){
    	int v1,v2;
    	int w;
    	cin>>n;
    	// 初始化图 
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			G[i][j] = 0;
    	// 初始化路径 
    	for(int i=1;i<=n;i++)
    		path[i] = -1;
    	// 初始化距离
    	for(int i=0;i<=n;i++)
    		dist[i] = 100000;
    	// 初始化收录情况 
    	for(int i=1;i<=n;i++)
    		vis[i] = 0;
    	cin>>m;
    	// 初始化点
    	for(int i=0;i<m;i++){
    		cin>>v1>>v2>>w;
    		G[v1][v2] = w;  // 有向图 
    	}
    }
    void init(int i){
    	dist[i]=0;
    	vis[i]=1;
    	for(int j=1;j<=n;j++){
    		if(G[i][j]){
    			dist[j]=G[i][j];
    			path[j]=i;
    		}
    	}
    }
    int  findMin(int v){
    	int mini=0;
    	for(int i=1;i<=n;i++){
    		if(i!=v&&!vis[i]&&dist[i]<dist[mini])mini=i;
    	} 
    	return mini;
    }
    void Dijkstra(int v){
    	init(v);
    	while(true){
    		int mini=findMin(v);//第一次找出来的就是v
    		if(!mini)break;
    		vis[mini]=1;
    		for(int i=1;i<=n;i++){
    			if(!vis[i]&&G[mini][i]&&G[mini][i]+dist[mini]<dist[i]){
    				dist[i]=G[mini][i]+dist[mini];
    				path[i]=mini;				
    			}
    		} 
    	}
    }
    void output(){
    	for(int i=1;i<=n;i++)
    		cout<<dist[i]<<" ";
    	cout<<endl;
    	for(int i=1;i<=n;i++)
    		cout<<path[i]<<" ";
    	cout<<endl;
    }
    int main(){
    	build();
    	Dijkstra(1);
    	output();
    	
    }
    

    多源最短路径Floyd算法

    核心就是贪心,如果i,j之间不能直接相通,dist[i][j]就化成无穷大,再慢慢的取减小

    void Floyd(){
        for( i = 0; i < N; i++ )
            for( j = 0; j < N; j++ ){
                D[i][j] = G[i][j];
                path[i][j] = -1;
            }
        for( k = 0; k < N; k++ )
            for( i = 0; i< N; i++)
                for( j = 0; j < N; j++ )
                	if( D[i][k] + D[k][j] < D[i][j] ) {
                		D[i][j] = D[i][k] + D[k][j];
                        path[i][j] = k;
                    }
    }
    
    

    列子:

    #include<bits/stdc++.h>
    using namespace std;
    int dist[1000][1000]={0};
    int G[1000][1000]={0};
    int path[1000][1000]={0}; 
    int n,m;
    void init(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			G[i][j]=100000;
    		}
    	}
    	cin>>m;
    	for(int i=1;i<=m;i++){
    		int v1,v2,w;
    		cin>>v1>>v2>>w;
    		G[v1][v2]=w;
    		G[v2][v1]=w;
    	}
    }
    void floyd(){
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			dist[i][j]=G[i][j];
    			path[i][j]=-1;
    		}
    	}
    	for(int k=1;k<=n;k++){
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=n;j++){
    				if(dist[i][k]+dist[k][j]<dist[i][j]){
    					dist[i][j]=dist[i][k]+dist[k][j];
    					path[i][j]=k;
    				}
    			}
    		}
    	}
    }
    void output(){
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    		    cout<<dist[i][j]<<" ";
    		} 
    		cout<<endl;
    	}
    }
    int main(){
    	init();
    	floyd();
    	output();
    } 
    

    习题1 哈利波特的考试

    在这里插入图片描述

    6 11
    3 4 70
    1 2 1
    5 4 50
    2 6 50
    5 6 60
    1 3 70
    4 6 60
    3 6 80
    5 1 100
    2 4 60
    5 2 80
    
    
    4 70
    

    简单来说就是,找每个节点到其他节点的最长距离,并在这些最长距离中找一个最小值

    #include<bits/stdc++.h>
    using namespace std;
    int dist[1000][1000]={0};
    int G[1000][1000]={0};
    int n,m;
    void init(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			G[i][j]=1000000;
    		}
    	}
    	cin>>m;
        for(int i=1;i<=m;i++){
        	int v1,v2,w;
        	cin>>v1>>v2>>w;
        	G[v1][v2]=w;
        	G[v2][v1]=w;
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			dist[i][j]=G[i][j];
    		}
    	}	
    }
    void floyd(){
    	init();
    	for(int k=1;k<=n;k++){
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=n;j++){
    				if(dist[i][k]+dist[k][j]<dist[i][j]){
    					dist[i][j]=dist[i][k]+dist[k][j];
    				}
    			}
    		}
    	}
    }
    int find1(int v){
    	int m=-10000;
    	for(int i=1;i<=n;i++){
    		if(i!=v){
    			m=max(m,dist[v][i]);
    		}
    	}
    	return m;
    }
    void find(){
    	int m=1000000;
    	int mi=0;
    	for(int i=1;i<=n;i++){
    		int l=find1(i);
    		if(m>l){
    			m=l;
    			mi=i;
    		}
    	}
    	cout<<m<<" "<<mi;
    }
    void output(){
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    		    cout<<dist[i][j]<<" ";
    		} 
    		cout<<endl;
    	}
    }
    int main(){
    	floyd();
    	//output();
    	find();
    }
    
    
    

    旅游规划

    在这里插入图片描述

    4 5 0 3
    0 1 1 20
    1 3 2 30
    0 3 4 10
    0 2 2 20
    2 3 1 20
    
    3 40
    

    分析:两个权值就用两个数组保存,利用单源有权图的算法即可

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,s1,d;
    int dist[10000]={0};
    int value[1000]={0};
    int cost[1000][1000]={0};
    int len[1000][1000]={0};
    int vis[1000]={0};
    void create(){
    	cin>>n>>m>>s1>>d;
    	for(int i=0;i<n;i++){
    		dist[i]=100000;
    	}
    	for(int i=0;i<m;i++){
    		int l1,l2,v1,v2;
    		cin>>l1>>l2>>v1>>v2;
    		cost[l1][l2]=v2;
    		len[l1][l2]=v1;
    	}
    }
    void init(int s){
    	for(int i=0;i<n;i++){
    		if(i!=s&&len[s][i]){
    			dist[i]=len[s][i];
    			value[i]=cost[s][i];
    		}
    	}
    }
    int findmin(int s){
    	int mini=-1;
    	int m=100000;
    	for(int i=0;i<n;i++){
    		if(i!=s&&!vis[i]&&dist[i]<m){
    			m=dist[i];
    			mini=i;
    		}
    	}
    	return mini;
    }
    void find(int s){
    	init(s);
    	while(true){
    		int i=findmin(s);
    		if(i==-1)break;
    		vis[i]=1;
    		for(int j=0;j<n;j++){
    			if(!vis[j]&&len[i][j]){
    				if(dist[i]+len[i][j]<dist[j]){
    					dist[j]=dist[i]+len[i][j];
    					value[j]=value[i]+cost[i][j];
    				}else if(dist[i]+len[i][j]==dist[j]&&value[i]+cost[i][j]<value[j]){
    					value[j]=value[i]+cost[i][j];
    				}
    			}
    		}
    	}
    }
    int main(){
    	create();
    	find(s1);
    	cout<<dist[d]<<" "<<value[d];
        
    }
    
    
    
    展开全文
  • 给定一个n个点m条边的有向中可能存在重边自环,所有边权均为正值。 请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。 输入格式 第一行包含整数nm。 接下来m行每行包含三个整数x,y...
  • 单源最短路:即一个点到任意点的最短路径 多源最短路:即任意一点到任意一点的最短路径 Dijkstra算法: 这个算法是通过点去更新最短路,每次找离源点最近的一个顶点,然后以该顶点为中心进行扩展,最终找到源点到...
  • 代码中所对应的:最小生成树:涉及到的知识:1. Dijkstra算法。2. Floyd算法。3. 无向有权的建立。4. Prim算法。//use邻接矩阵存储的的最短路径问题 #include &lt;iostream&gt; #include &lt;...
  • 最短路径问题(单源和多源点)

    千次阅读 2019-06-09 19:50:34
    最短路径问题(单源和多源点) 单源点 Bellmanford算法 Dijkstra算法 多源点 动态规划 FloyWarshall算法 单源点 Bellmanford算法 算法思想: 先初始化原点d[ ] = INF ,d[s] = 0 。 对所有的边进行松弛,每一...
  • 最短路径(单源多源等形式)
  • 给定一个由 0 1 组成的矩阵,找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。 示例 1: 输入: [[0,0,0], [0,1,0], [0,0,0]] 输出: [[0,0,0], [0,1,0], [0,0,0]] 示例 2: 输入: [[0,0,0], [0...
  • 就是二源 bfs 的扩撒: * 为啥要用多源 bfs:我的单源也可以过啊,只不过速度有点…,其实多源 bfs 也是通过事先将多个源点添加到队列中,然后进行单源 bfs 的。 题目中的 「曼哈顿距离」,其实就是对广度优先...
  • 多个等价起始状态的BFS 改变一下思路,将所有的1全部作为起点加入队列,然后去遍历整张,最后一个被搜索到的0就是离所有1曼哈顿距离最大的。 ( 图片来自互联网 ) 时间复杂度: O(n2)O(n^2)O(n2) const int dx[]...
  • 一、题目描述 输入样例: 3 4 0001 0011 0110 输出样例: ...我们不必从 0 开始,我们实际上可以从每个 1 开始,每个 1 自己的距离是 0,然后不断 bfs 扩展。遇到 0,则将其坐标的值改为当前 cur 点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,029
精华内容 1,211
关键字:

单源和多源图