精华内容
下载资源
问答
  • Dijkstra算法单源最短路径Java实现

    千次阅读 2017-07-07 10:51:47
    如果所采用实现方式合适,Dijkstra算法运行时间要低于前面所说Bellman_Ford...算法重复从结点集V-S中选择最短路径估计最小结点u,u加入到集合S,然后对所有从u发出边进行松弛(有关松弛操作可见http://bl

    如果所采用的实现方式合适,Dijkstra算法的运行时间要低于前面所说的Bellman_Ford算法,但是Dijkstra算法要求图中没有负边。Dijkstra算法在运行过程中维持的关键信息是一组结点集合S。从源结点s到该集合中每个结点之间的最短路径已经被找到。算法重复从结点集V-S中选择最短路径估计最小的结点u,将u加入到集合S,然后对所有从u发出的边进行松弛(有关松弛操作可见http://blog.csdn.net/john_bian/article/details/74612722)。下面是《算法导论》书中所给的伪代码:


    在这个实现方式中,我们使用了一个最小优先队列Q来保存结点集合,每个结点的关键值为其d值。下面则是运用Dijkstra算法求解单源最短路径的过程的一个例子。


    以下是用Java代码的具体实现

    package test7;
    
    /**
     * 边
     * @author sdu20
     *
     */
    public class Edge {
    	
    	private int v1;
    	private int v2;
    	private int weight;
    	
    	public Edge(int v1,int v2,int weight){
    		this.v1 = v1;
    		this.v2 = v2;
    		this.weight = weight;
    	}
    	
    	public boolean equals(Edge edge){
    		return this.v1==edge.getV1() && this.v2==edge.getV2() &&this.weight == edge.getWeight();
    	}
    	
    	public int getV1(){
    		return v1;
    	}
    	
    	public int getV2(){
    		return v2;
    	}
    	
    	public int getWeight(){
    		return weight;
    	}
    	
    	public String toString(){
    		String str = "[ "+v1+" , "+v2+" , "+weight+" ]";
    		return str;
    	}
    
    }
    

    package test7;
    
    import java.util.*;
    
    /**
     * Dijkstra算法求解单源最短路径
     * @author sdu20
     *
     */
    
    public class Graph {
    
    	private LinkedList<Edge>[] edgeLinks;
    	private int vNum;	//顶点数
    	private int edgeNum;	//边数
    	private int[] distance;	//存放v.d
    	private int[] prenode;	//存放前驱节点
    	private LinkedList<Integer> S;	//已经求到最短路径的顶点集合
    	private LinkedList<Integer> Q;	//尚未求到最短路径的顶点集合
    	public static final int INF = 10000;	//无穷大
    	public static final int NIL = -1;	//表示不存在
    	
    	public Graph(int vnum){
    		this.vNum = vnum;
    		edgeLinks = new LinkedList[vnum];
    		edgeNum = 0;
    		distance = new int[vnum];
    		prenode = new int[vnum];
    		for(int i = 0;i<vnum;i++)
    			edgeLinks[i] = new LinkedList<>();
    	}
    	
    	public void insertEdge(Edge edge){		
    		int v1 = edge.getV1();
    		edgeLinks[v1].add(edge);
    		edgeNum++;		
    	}
    	
    	public void bianli(){
    		System.out.println("共有 "+vNum+" 个顶点, "+edgeNum+" 条边");
    		for(int i = 0;i<vNum;i++){
    			LinkedList<Edge> list = (LinkedList<Edge>) edgeLinks[i].clone();
    			while(!list.isEmpty()){
    				Edge edge = list.pop();
    				System.out.println(edge.toString());
    			}
    		}
    	}
    	
    	/**
    	 * 对最短路径估计和前驱节点进行初始化
    	 * @param start
    	 */
    	public void INITIALIZE_SINGLE_SOURCE(int start){
    		for(int i = 0;i<vNum;i++){
    			distance[i] = INF;
    			prenode[i] = NIL;
    		}
    		distance[start] = 0;
    	}
    	
    	/**
    	 * 松弛
    	 * @param edge
    	 */
    	public void RELAX(Edge edge){
    		int v1 = edge.getV1();
    		int v2 = edge.getV2();
    		int w = edge.getWeight();
    		if(distance[v2]>distance[v1]+w){
    			distance[v2] = distance[v1]+w;
    			prenode[v2] = v1;
    		}
    	}
    	
    	/**
    	 * Dijkstra算法实现
    	 * @param start
    	 */
    	public void DIJKSTRA(int start){
    		
    		INITIALIZE_SINGLE_SOURCE(start);
    		
    		S = new LinkedList<>();
    		Q = new LinkedList<>();
    		for(int i = 0;i<vNum;i++){
    			Q.add(i);
    		}
    		
    		while(!Q.isEmpty()){
    			int u = EXTRACT_MIN(Q);
    			S.add(u);
    			LinkedList<Edge> list = (LinkedList<Edge>) edgeLinks[u].clone();
    			while(!list.isEmpty()){
    				Edge edge = list.pop();
    				RELAX(edge);
    			}
    		}
    		
    		ShowResult();
    	
    	}
    	
    	private int EXTRACT_MIN(LinkedList<Integer> q){
    		
    		if(q.isEmpty())
    			return -1;
    		
    		int min = q.getFirst();
    		for(int i = 0;i<q.size();i++){
    			int v = q.get(i);
    			if(distance[min]>distance[v]){
    				min = v;
    			}
    		}
    		int min2 = min;
    		q.remove(q.indexOf(min));
    		return min;
    	}
    	
    	private void ShowResult(){
    		System.out.println("=========Result==========");
    		Stack<Integer>[] routes = new Stack[vNum];
    		for(int i = 0;i<vNum;i++){
    			routes[i] = new Stack<>();
    			int j = i;
    			while(j != NIL){
    				routes[i].push(j);
    				j = prenode[j];
    			}
    			
    			System.out.print(i+"("+distance[i]+") : ");
    			while(!routes[i].isEmpty()){
    				int k = routes[i].pop();
    				System.out.print("-->"+k);
    			}
    			System.out.println();
    		}	
    	}
    }
    

    package test7;
    
    public class Main {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		bookGraph();
    	}
    	
    	private static void bookGraph(){
    		Graph graph = new Graph(5);
    		Edge[] edges = new Edge[10];
    		
    		edges[0] = new Edge(0,1,10);
    		edges[1] = new Edge(0,3,5);
    		edges[2] = new Edge(1,2,1);
    		edges[3] = new Edge(1,3,2);
    		edges[4] = new Edge(2,4,4);
    		edges[5] = new Edge(3,1,3);
    		edges[6] = new Edge(3,2,9);
    		edges[7] = new Edge(3,4,2);
    		edges[8] = new Edge(4,0,7);
    		edges[9] = new Edge(4,2,6);
    		
    		for(int i = 0;i<10;i++)
    			graph.insertEdge(edges[i]);
    		
    		graph.bianli();
    		graph.DIJKSTRA(0);
    	}
    
    }
    

    运行截图如下所示


    展开全文
  •  Dijkstra算法解决是带权重有向图上单源最短路径问题,所谓单源最短路径,就是固定一个顶点为源点,源点到其他每个顶点的最短路径,该算法要求图上所有边权值为非负值。  Dijkstra算法在运行过程中,...

    Dijkstra算法

            Dijkstra算法解决的是带权重的有向图上单源最短路径问题,所谓单源最短路径,就是固定一个顶点为源点,求源点到其他每个顶点的最短路径,该算法要求图上所有边的权值为非负值。

            Dijkstra算法在运行过程中,将整个图划分为两个点集合S与T,其中源点s到点集合S中所有顶点的最短路径已经被找到,而s到T中所有顶点的最短路径还没有被找到。初始时,集合S中只有源点s;算法重复地从点集合T中选择当前长度最小的一条最短路径的顶点u,将u加入到集合S,然后修改从顶点0到T中各顶点的最短路径长度;重复这一步骤,直到所有顶点都加入到集合S中,算法结束。在下面给出的伪代码中,我们利用一个最小优先队列实现该算法,优先队列中保存的元素为(源点到顶点u的最短距离d[u],顶点u),优先队列中的元素按照关键字d[u]升序排列。

    初始化,清除所有点的标号

    令d[0] = 0,其他d[i] = INF

    源点s入队列

    队列非空{

        在所有未标号的顶点中选择d值最小的顶点u

        u出队

        给顶点u标号

        对于所有从u出发的边(u,v),更新d[v] = min{d[v],d[u] + w(u,v)}

    }

    Dijkstra算法的执行过程如下所示:


    1.源点0入队


    2.源点0出队,更新d[1] = 1、d[2] = 7,顶点1、2入队


    3.顶点1出队,更新d[3] = 10、d[5] = 16,顶点3、5入队


    4.顶点2出队,更新d[4] = 11,顶点4入队


    5.顶点3出队,更新d[5] = 15


    6.顶点4出队,更新d[5] = 14


    7.顶点5出队,算法结束

            使用邻接矩阵实现的Dijkstra算法的时间复杂度为O(|V|^2),而使用邻接表的话,更新最短距离只需要访问每条边一次即可,因此这部分的时间复杂度为O(|E|)。但是每次要枚举所有顶点来查找下一个使用的顶点,因此最终复杂度还是O(|V|^2)。使用堆优化后,每次从堆中取出的最小值都是下一次要使用的顶点。这样堆中的元素共有O(|V|)个,更新和取出数值的操作有O(|E|)次,因此整个算法的复杂度是O(|E|log|V|)。

            下面给出使用C++实现的Dijkstra算法核心代码

    typedef pair<int,int> P;//first是最短距离,second是顶点的编号
    struct edge
    {
        int to;
        int dis;//权值
        edge(int to,int dis)
        {
            this -> to = to;
            this -> dis = dis;
        }
    };
    vector<edge> G[maxn];
    int d[maxn];//最短距离
    int V,E;//V顶点数,E边数
    //初始化
    void init()
    {
        for(int i = 0;i < V;i++)
            G[i].clear();
    }
    //建图
    void add_edge(int from,int to,int dis)
    {
        G[from].push_back(edge(to,dis));
    }
    
    void dijkstra(int s)
    {
        //通过指定greater<P>参数,堆按照first从小到大的顺序取出值
        priority_queue<P,vector<P>,greater<P> > que;
        for(int i = 0;i < V;i++)
            d[i] = INF;
        d[s] = 0;
        que.push(P(0,s));
        while(que.size()){
            P p = que.top();
            que.pop();
            int v = p.second;
            if(d[v] < p.first)
                continue;
            for(int i = 0;i < (int)G[v].size();i++){
                edge e = G[v][i];
                if(d[e.to] > d[v] + e.dis){
                    d[e.to] = d[v] + e.dis;
                    que.push(P(d[e.to],e.to));
                }
            }
        }
    }


    PS:水平有限,如有错误,请路过的各位指正,谢谢!

    展开全文
  • 给定数字n,m(1<=n,m<=500000) n变为n*2花费2,n变为n-3花费3,要求过程中所有数字都在[1,500000]区间内。 求将n变为m最少花费 ...转换为n至m的最短路径 1 #include <bi...

    给定数字n,m(1<=n,m<=500000)

    将n变为n*2花费2,将n变为n-3花费3,要求过程中所有数字都在[1,500000]区间内。

    求将n变为m的最少花费

    思路:建图

    将每个数字视为图中的点,数字之间的转换视为图中的边,有向图。

    500000个点,(i,i*2)权值为2,(i,i-3)权值为3

    转换为求n至m的最短路径

     1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const long long INF = 0x3f3f3f3f3f3f3f3f;
     4 int n,m;
     5 vector<pair<long long,int>> edge[500001];
     6 long long dis[500001];
     7 typedef pair<long long,int> P;//first 最短距离,second顶点编号
     8 
     9 void dijkstra(int s)
    10 {
    11     memset(dis,INF, sizeof(dis));
    12     priority_queue<P,vector<P>,greater<P>> que; //最小堆
    13     que.push(P(0,s));
    14     dis[s]=0;
    15     while(que.size())
    16     {
    17         P p=que.top();que.pop();
    18         int v = p.second;
    19         //vis[v]=1;
    20         if(dis[v]<p.first)continue;
    21         for(int i=0;i<edge[v].size();i++)
    22         {
    23             int to = edge[v][i].second;
    24             long long cost = edge[v][i].first;
    25             //if(!vis[to]&&dis[to]>dis[v]+cost)
    26             if(dis[to]>dis[v]+cost)
    27             {
    28                 dis[to]=dis[v]+cost;
    29                 que.push(P(dis[to],to));
    30             }
    31         }
    32     }
    33     if(dis[m]==INF)
    34         cout<<-1<<endl;
    35     else
    36         cout<<dis[m];
    37 }
    38 
    39 int main() {
    40     cin >> n >> m;
    41     for (int i = 1; i <= 500000; i++)
    42     {
    43         if(2*i<500000)
    44             edge[i].push_back(make_pair(2,2*i));
    45         if(i-3>0)
    46             edge[i].push_back(make_pair(3,i-3));
    47     }
    48     dijkstra(n);
    49     return 0;
    50 }

     思路2:暴力BFS

     1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const int INF = 0x3f3f3f3f;
     4 typedef long long LL;
     5 int n,m;
     6 struct node
     7 {
     8     int x;
     9     LL cost;
    10 };
    11 int vis[500002];
    12 
    13 int main() {
    14     cin >> n >> m;
    15     node cur,now;
    16     cur.x=n,cur.cost=0;
    17     queue<node> q;
    18     q.push(cur);
    19     LL ans=1e18;
    20     vis[cur.x]=1;
    21     while(q.size())
    22     {
    23         now=q.front();q.pop();
    24         if(now.x==m)
    25         {
    26             ans=min(ans,now.cost);
    27             continue;//剪枝
    28         }
    29         cur.x=now.x*2;
    30         cur.cost=now.cost+2;
    31         if(cur.x<=500000&&!vis[cur.x])
    32         {
    33             vis[cur.x]=1;
    34             q.push(cur);
    35         }
    36         cur.x=now.x-3;
    37         cur.cost=now.cost+3;
    38         if(cur.x>0&&!vis[cur.x])
    39         {
    40             vis[cur.x]=1;
    41             q.push(cur);
    42         }
    43     }
    44     if(ans==1e18) printf("-1\n");
    45     else cout<<ans<<endl;
    46     return 0;
    47 }

     

    转载于:https://www.cnblogs.com/demian/p/9196508.html

    展开全文
  • 1由于是所有黑像素的点到白像素的最短距离所以采用适合于整体计算floyd算法比较好但floyd算法的时间复杂度为On3m3不能满足时间要求 2考虑用单源最短路径的算法对于每一点进行一次宽度优先搜索该点到其他各点的...
  • 迪杰斯特拉算法解决是带权重有向图上单源最短路径问题,该算法要求所有边权重都为非负值,其在运行过程中维持关键信息是一组节点集合S。算法重复从结点集V-S中选择最短路径估计最小结点u,u加入到集合S...

    迪杰斯特拉算法解决的是带权重的有向图上单源最短路径问题,该算法要求所有边的权重都为非负值,其在运行过程中维持的关键信息是一组节点集合S。算法重复从结点集V-S中选择最短路径估计最小的结点u,将u加入到集合S,然后对所有从u发生的边进行松弛,运行结束后,从源节点到集合S中每个结点之间的最短路径已经被找到。
    下面,通过一个实例讲解该过程!

    一、示例详解

    在这里插入图片描述
    如图,是一个有向无环图,假定出发点为V1,迪杰斯特拉算法将算出V1到其他所有点的最短路径,则所求V1到终点的最短路径也可得到,该算法主要完成以下几步:

    找到V1
    得到以V1出发的邻接点的最短距离,将V1加到S集合中(代码中通过vis数组标记)
    从S集合之外的点中找到距离最短者,对以其为出发点的邻接点进行松弛操作,若距离被更新,则记录前驱
    重复3,直到所有点被S集合收录
    

    完成后,将得到V1到所有点的最短距离,同时,通过每一个点记录的前驱得到最短路径。

    1.问题

    1.1 松弛操作是啥?

    松弛操作意味着比起原来的路径,找到了一条距离更短的路,则将原来点的距离更新为新的距离。注意本文中某个点的距离全部指的是从出发点即V1到该点的距离。代码如下:

     if(dis[j]>dis[k]+map[k][j])
     {
          dis[j]=dis[k]+map[k][j];
          path[j]=k;
     }
    

    1.2 为啥每个点记录前驱能用于V1到所有终点?

    我的理解是最短路是由最短路+某一条固定路组成,所以前驱适用全部点,比如该图中V1到V7的最短路径为V1->V2->V3->V5->V6->V7,因为V6->V7的距离固定为50,所以V7的最短路径中V1->V6的一段必然是V1->V6的最短路径,因此每个结点只需记录一个前驱。要想打印出路径,从终点开始一次次找前驱即可,可通过递归实现。代码如下:

    void print(int x)//x为终点
    {
        if(x == -1) return;
        //递归
        print(path[x]);
        printf("%d->",x);
    }
    

    2. 算法过程

    程序运行过程中,数据的更新情况如图所示:
    在这里插入图片描述

    红色数据代表每次迭代中被更新的数据,下标代表了结点前驱。由上图可得,当所有结点加入S后,就得到了V1到所有结点的最短距离和最短路径,例如V1到V7的最短距离为130,V7的前驱为V6,V6的前驱为V5,V5的前驱为V3,V3的前驱为V2,V2的前驱为V1,则V1到V7的最短路径为V1->V2->V3->V5->V6->V7。

    3. 算法复杂度分析

    在这里插入图片描述


    二、代码实现

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    
    /*问题描述:
     * 输入n和m,代表n个节点,m条边,然后是m行输入,每行有x,y,z,代表x到y的路距离为z。
     * 问题:从1出发到各点的最短路径。
     * 测试样例:
    7 12
    1 2 20
    1 3 50
    1 4 30
    2 3 25
    2 6 70
    3 4 40
    3 6 50
    3 5 25
    4 5 55
    5 6 10
    5 7 70
    6 7 50
     */
    using namespace std;
    const int maxn = 100;
    int map[maxn][maxn];
    int dis[maxn];
    int path[maxn];
    int vis[maxn];//记录更新过的点
    int n;
    void dijk(int s)
    {
        //初始化
        memset(path,-1,sizeof(path));
        /*INF使用0x3f3f3f3f的好处:
         * 1:满足无穷大加一个有穷的数依然是无穷大(在DijKstra算法松弛操作中避免了溢出而出现负数)
         * 2:满足无穷大加无穷大依然是无穷大(两个0x3f3f3f3f相加并未溢出)
         * 3:初始化时,由于每一个字节为0x3f,所以只需要memset(buf,0x3f,sizeof(buf))即可
         */
        memset(dis,0x3f,sizeof(dis)); //初始化为无穷大
        memset(vis,0,sizeof(vis));
        dis[s] = 0; //自身到自身的距离为0
        while(1)
        {
            int k = 0;
            for(int j = 1; j <= n; j++)
            {
                if(!vis[j]&&dis[j]<dis[k])//找未收录顶点中dis值最小的
                    k=j; //这里第一次找到的是起点
            }
            if(!k) return; //没有未收录的点,则返回
            vis[k] = 1;
            //松弛操作
            for(int j = 1; j <= n; j++)
            {
                //第一次循环只有起点的邻接点距离被更新,每次都更新新找到的点的邻接点
                if(dis[j]>dis[k]+map[k][j])
                {
                    dis[j]=dis[k]+map[k][j];
                    path[j]=k;//路径被改变,重新记录前驱,最短路是由最短路+某一条固定路组成,所以前驱是有效的
                }
            }
        }
    }
    
    void print(int x)//x为终点
    {
        if(x == -1) return;
        //递归
        print(path[x]);
        printf("%d->",x);
    }
    int main()
    {
        int m,x,y,z,order;
        scanf("%d%d",&n,&m);
        memset(map,0x3f,sizeof(map));
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            map[x][y] = z;
        }
        dijk(1);
        scanf("%d",&order);//order为终点
        print(path[order]);
        printf("%d\n",order);
        //打印最短距离
        printf("%d\n",dis[order]);
        return 0;
    }
    
    
    

    参考

    Dijkstra算法及代码详解

    展开全文
  • 深搜和广搜简单概述和实现方式

    千次阅读 2018-05-24 15:27:19
    广搜(BFS):广搜一般是用于的最短路径,比如迷宫中走到某一点最短距离,或者某个字符串交换达到目标字符串最少次数,解个数一般是为单一,可以把搜索整个过程想象成一棵树,要求的解就是其中某一...
  • 医院选址问题

    2012-01-06 10:38:18
    2.对最短路径长度矩阵每列大值,即得到各顶点偏心度; 3.具有最小偏心度顶点即为所。 【思考题】图存储结构和算法设计需要一定灵活性和技巧。从医院选址问题求解过程,你有什么感想? 答:通过...
  • 差分约束系统

    2011-09-11 17:18:00
    小结: 差分约束就是用最短(最长路径)来解决满足一系列约束条件问题最优解,首先约束条件必须满足一定限制,即每个约束条件系数只能为1,-1这样不等式。...如果题目要求出最小值,我们所有不等式转化...
  • 29、 已知如下图,写出用动态规划求最短路径的递推关系式,并写出求从源点A0到终点A3 的最短路径过程。给出求解算法。 6 A1 A2 5 5 2 A0 A3 3 4 4 B1 B2 5 搜索与遍历问题 30、 已知有向图G=,E>,试设计一...
  • 最小费用流 SPFA 多路增广

    千次阅读 2012-11-04 20:45:11
    一直都只会费用流暴力增广,但这次被卡住了:在一个二分图上暴力增广,增广次数至少也是 O...每次增广完的路径节点要求将其标记清零:因为其有可能再次出现在最短路网中。接着像 dinic 一样:找到增广路上最早
  • 数据结构课设

    2013-01-03 02:51:25
    任务:可以读入一个任意大小迷宫数据,分别用广度和深度搜索方法出一条走出迷宫的路径,并将路径输出(最佳路径); 要求:以较为直观方式显示结果 3、 Huffman编码 任务 :对一篇英文文章,统计各字符...
  • 算法导论(part2)

    2010-09-09 22:54:12
    ·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...
  • 算法导论(part1)

    2010-09-09 22:51:05
    ·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...
  •  (2) 查询图中任意两个景点间的最短路径。  (3) 查询图中任意两个景点间所有路径。  (4) 增加、删除、更新有关景点和道路信息。 [选作内容]  (1) 多个景点最佳(最短)游览路径。  (2) ...
  • 动态规划 ppt演示

    热门讨论 2008-09-30 13:06:29
    Bitonic旅行路线问题是欧几里德货郎担问题简化,这种旅行路线先从最左边开始,严格地由左至右到最右边点,然后再严格地由右至左到出发点,路程最短的路径长度。图1(b)给出了七个点问题解。 请设计一种...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    4、用邻接矩阵或邻接图实现一个有向图存储,并实现单源最短路径算法实现(这个类一个成员函数),并能输出该图关键路径。 注:1、要用面向对象方法设计代码; 2、一个图是一个类实例; 3、类...
  • 大话数据结构

    2018-12-14 16:02:18
    100个人高考成绩平均分与全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高...
  • 消息驱动Bean必须实现两个接口MessageDrivenBean和MessageListener 在对象创建的过程中将被容器调用,onMessage函数方法接收消息参数,其强制转型为合适的消息类型,同时打印出消息的内容。同时一个mail note被...
  • JAVA上百实例源码以及开源项目

    千次下载 热门讨论 2016-01-03 17:37:40
     在对象创建的过程中将被容器调用,onMessage函数方法接收消息参数,其强制转型为合适的消息类型,同时打印出消息的内容。同时一个mail note被发送给消息发送者,发送一个e-mail通知给由recipient参数确定的e-...
  • 南理工初试试题

    2015-09-08 09:48:55
    2) (3分) 按Dijkstra算法,给出从顶点1(顶点标号从1计)到其余顶点的最短路径长度以及经过中间点。 3)(3分)画出该图邻接表存储结构示意图。 4)(3分)画出对应无向图最小生成树,给出生成树边权之和。(如果...
  • c语言编写单片机技巧

    2009-04-19 12:15:17
    在应用中,一般是微处理器装配在专门设计电路板上,在母板上只保留和嵌入式相关功能即可,这样可以满足嵌入式系统体积小和功耗低的要求。目前嵌入式处理器主要包括:PowerPC、Motorola 68000、ARM系列...

空空如也

空空如也

1 2
收藏数 27
精华内容 10
关键字:

要求将求最短路径的过程