> 文档中心 > Dijkstra求最短路(朴素)邻接表+邻接矩阵

Dijkstra求最短路(朴素)邻接表+邻接矩阵

邻接表:稀疏图

#include#include#includeusing namespace std;const int N = 100010;int h[N], e[N], ne[N], w[N], idx;//邻接表int d[N];bool st[N];int n, m;void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], h[a] = idx, w[idx] = c;idx++;}int dijkstra(){d[1] = 0;for (int i = 0; i < n - 1; i++) {int t = -1;for (int j = 1; j  d[j]))t = j;}st[t] = true;for (int j = h[t]; j != -1; j = ne[j]) {int k = e[j];d[k] = min(d[k], d[t] + w[j]);}}if (d[n] != 0x3f3f3f3f)return d[n];elsereturn -1;}int main(){memset(st, false, sizeof st);memset(h, -1, sizeof h);memset(d, 0x3f, sizeof d);cin >> n >> m;while (m--) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << dijkstra() << endl;return 0;}

邻接矩阵:稠密

#include#include#includeusing namespace std;const int N = 1010;int g[N][N];//图int d[N];//i点到1的距离 int n,m;bool st[N];//到1的距离是否已经被确定 int dijkstra(){memset(d,0x3f,sizeof d);memset(st,false,sizeof st);d[1] =0;for(int i =0;i < n-1;i++){//控制循环次数 为什么是n-1次 ?int t = -1;for(int j =1;j  d[j])){//t==-1的意思是控制第一个被确定的点一定是1 t = j;} }for(int j = 1;j >n>>m;while(m--){int a,b,c;cin>>a>>b>>c;g[a][b] = min(g[a][b],c);} cout<<dijkstra()<<endl; return 0;}