重庆网站建设哪个平台好,甘肃项目信息网,火车头采集器和wordpress,泉港做网站公司一#xff1a;前言
本次题解先展示用邻接矩阵做的#xff0c;但其会出现内存超限#xff0c;因为确实是临界矩阵在数据很大的时候相比临界表是耗内存的#xff0c;但是以前习惯用临界矩阵了#xff0c;所以一上来就用临界矩阵做了#xff0c;后来上网查了后知道邻接矩阵…一前言
本次题解先展示用邻接矩阵做的但其会出现内存超限因为确实是临界矩阵在数据很大的时候相比临界表是耗内存的但是以前习惯用临界矩阵了所以一上来就用临界矩阵做了后来上网查了后知道邻接矩阵会内存超限所以后来又用邻接表写了一遍。
二题目
请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点编号为0至n-1以顶点0作为源点。
输入格式: 输入第一行为两个正整数n和e分别表示图的顶点数和边数其中n不超过20000e不超过1000。接下来e行表示每条边的信息每行为3个非负整数a、b、c其中a和b表示该边的端点编号c表示权值。各边并非按端点编号顺序排列。
输出格式: 输出为一行整数为按顶点编号顺序排列的源点0到各顶点的最短路径长度不含源点到源点每个整数后一个空格。如源点到某顶点无最短路径则不输出该条路径长度。
输入样例:
4 4
0 1 1
0 3 1
1 3 1
2 0 1输出样例:
1 1 三介绍dijkstra算法
1.dijkstra
无论你用哪种数据结构存储数据其算法思想是一样的dijkstra算法单源点最短路径其在更新的阶段体现了贪心每次都找最优的结即最小的路径
2做题思路
思路1.首先读题分析到 这是一个有向图 2.单源点最短路径确定一个点为源点其到其他点的最短路径本题当中 因为是有向图当没有最短路径就不输出了
分析示例 4 4 0 1 1 0 3 1 1 3 1 2 0 1
输出为 1 1
这是0 到 1 的最短路径和0到3的最短路径 而 0到 2无路径 2到0有路径 3.本题我先用的是临界矩阵储存数据的会出现内存超限后来改为邻接表而体现贪心的部分是代码中的更新的部分每次都找最优解 4.具体代码流程需要自己分析示例图解这里有我分析的无向图的图解思路和有向图类似 懂了这个就懂了本题的写码思路了
3.图示以无向图为例和有向图思路是一致的 四上码
1.用邻接矩阵存储的数据会出现内存超限
/**思路1.首先读题分析到 这是一个有向图2.单源点最短路径确定一个点为源点其到其他点的最短路径本题当中因为是有向图当没有最短路径就不输出了分析示例 4 40 1 10 3 11 3 12 0 1 输出为 1 1 这是0 到 1 的最短路径和0到3的最短路径 而 0到 2无路径 2到0有路径 3.本题我用的是临界矩阵储存数据的而体现贪心的部分是代码中的更新的部分每次都找最优解 4.具体代码流程需要自己分析示例图解这里有我分析的无向图的图解思路和有向图类似懂了这个就懂了本题的写码思路了 */ #includebits/stdc.husing namespace std;typedef struct Graph * PtrGraph; typedef struct Graph{int Nv;int Ne;int Date[2276][2274];} graph;int infinite 99999;//初始化临界矩阵void CreateGraph(PtrGraph G){cin G-Nv G-Ne;//初始化临界矩阵 for(int i 0; i G-Nv; i){for(int j 0; j G-Nv; j){if(i j){G-Date[i][j] 0;} else{G-Date[i][j] infinite;//当两个点不相连的时候为无穷大 }} }//向临界矩阵中赋值for(int k 0; k G-Ne; k){int i,j,w;cin i j w;G-Date[i][j] w;//这里体现有向图即从 i 到 j 在临界矩阵中有值而从j到i无值 } } //验证输出临界矩阵 // void print_Graph(PtrGraph G) {// for(int i 0; i G-Nv; i){// for(int j 0; j G-Nv; j){// cout G-Date[i][j] ;// } // cout endl;// }// }//核心代码 体现贪心的代码 每次更新均找距离最短的点 void dijkstra(PtrGraph G){int dist[2001];//用于存储源点到各个点的最短距离int visited[2001];//用于记录已经访问了哪个点的 for(int i 0; i G-Nv; i){dist[i] G-Date[0][i];//题目给出了源点是 0 } visited[0] 1;//表示1已经访问过了//更新 while(1){int m -1;int min infinite;for(int i 0; i G-Nv; i){if(visited[i] ! 1 dist[i] min){min dist[i];m i; } } if(m -1){//如果m无变化,说明图中的各点已经更新完了 break;}visited[m] 1;for(int i 0; i G-Nv; i){if(visited[i] ! 1 min G-Date[m][i] dist[i]){//这里注意 min G-Date[m][i]//表示了一个源点到其最短的距离min的点//然后需要判断这个点到其他点的距离加上min和源点到其他点的距离进行比较更新dist[i] min G-Date[m][i];}} } for(int i 1; i G-Nv; i){if(dist[i] infinite)continue;else{cout dist[i] ; } } } int main(){PtrGraph G (PtrGraph)malloc(sizeof(struct Graph));CreateGraph(G);// print_Graph(G);dijkstra(G);}
2用邻接表存的正确结果
#includebits/stdc.h
using namespace std;
#define max 20001struct Node{int to;//指向边的结点 int val;//边的权值 int next;//指向下一个结点的下标
} node[max];int head[max],n,m,num 0;
int infinite 99999;//建立邻接表
void add(int from,int to,int val){num;node[num].to to;node[num].val val;node[num].next head[from];head[from] num;//更新head的值当再有从from连接的点 它的下一个为 num 坐标
} //dij算法
void dijkstra(){int dist[max];fill(dist, dist 20001, infinite);int vis[max] {0};for(int i head[0]; i ! 0; i node[i].next){//这里是选取源点为0的顶点将和其相连边的权值存进去了 dist[node[i].to] node[i].val; //比如0到1即 node[i].to 1表示的是顶点, node[i].val 1 表示0到1这条边的权值为1;dist[1] 1}vis[0] 1;while(1){int m -1;int min infinite;for(int i 0; i n; i){if(vis[i] ! 1 dist[i] min){min dist[i];m i;}}if(m -1){//已经遍历完了所有结点 break;}vis[m] 1;//确定m这个顶点 接下来遍历 m这个结点的链表 for(int i head[m]; i ! 0; i node[i].next){if(vis[node[i].to] ! 1 min node[i].val dist[node[i].to]){//vis[node[i].to] ! 1如果出现 1到2 和2到1这种情况那么当1已经遍历过在顶点为2的这个链表中就不用再遍历了dist[node[i].to] min node[i].val;} } } for(int i 0; i n; i){if(dist[i] ! infinite){cout dist[i] ;}}
} int main(){memset(head,0,sizeof(head));cin n m;for(int i 0; i m; i){int from,to,val;cin from to val;add(from,to,val);} //测试邻接表的数据是否正确
// for(int i 0; i n; i){
// cout i ;
// for(int j head[i]; j ! 0; j node[j].next){
// cout node[j].to node[j].val ;
// }
// cout endl;
// }dijkstra();}//4 4
//0 1 1
//0 3 1
//1 3 1
//2 0 1//邻接表输出的数据
//0 3 1 1 1
//1 3 1
//2 0 1
//3//4 5
//0 1 1
//1 3 2
//0 3 4
//0 2 2
//2 3 3 五知识速递如果兄弟们对邻接表不熟悉可以学习下哈
邻接表的用法
加油 兄弟们
