首页 > 其他分享 > 迪杰斯特拉方法实现最短路径

迪杰斯特拉方法实现最短路径

时间:2022-12-22 12:56:17浏览次数:49  
标签:pre int 路径 迪杰 最短 斯特拉 next 输入 dis

用迪杰斯特拉算法实现有向网的最短路径

输入格式:

第一行输入有向网的顶点和边数,第二行输入各顶点值,用空格间隔,第三行开始输入各条边的 两个点的及边上的权值,用空格间隔。最后一行输入要求路径的两个顶点。

输出格式:

输出最短路径经过的各顶点,中间用-->连接。

输入样例:

在这里给出一组输入。例如:

6 8
0 1 2 3 4 5
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
0 3

  

输出样例:

在这里给出相应的输出。例如:

0-->4-->3

  

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1010;
 
struct edge{
    int v,w;
    edge* next;
};
struct node{
    int k;
    edge* next;
}a[1010];
int n;
 
int find(int u){
    for(int i=0;i<n;i++){
        if(a[i].k==u){
            return i;
        }
    }
    return -1;
}
 
void add(int u,int v,int w){
    edge* e=new edge();
    e->v=v;
    e->w=w;
    e->next=a[u].next;
    a[u].next=e;
}
 
int dis[N],pre[N];
bool st[N];
 
void dijkstra(int u){
    memset(pre,-1,sizeof pre);
    memset(dis,0x3f,sizeof dis);
    dis[u]=0;
    for(int i=0;i<n-1;i++){
        int k=-1;
        for(int j=0;j<n;j++){
            if(st[j]==0&&(k==-1||dis[j]<dis[k])){
                k=j;
            }
        }
        if(dis[k]==0x3f3f3f3f){
            continue;
        }
        st[k]=1;
        for(edge* j=a[k].next;j!=NULL;j=j->next){
            int v=j->v,w=j->w;
            if(dis[v]>dis[k]+w){
                dis[v]=dis[k]+w;
                pre[v]=k;
            }
        }
    }
}
 
void showRoad(int v){
    if(pre[v]!=-1){
        showRoad(pre[v]);
        cout<<"-->"<<a[v].k;
    }else{
        cout<<a[v].k;
    }
}
 
int main(){
    int m;
    cin>>n>>m;
     
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        a[i].k=k;
    }
     
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        int uu=find(u),vv=find(v);
        add(uu,vv,w);
    }
     
    int u,v;
    cin>>u>>v;
    dijkstra(u);
     
    showRoad(v);
     
    return 0;
}

  

标签:pre,int,路径,迪杰,最短,斯特拉,next,输入,dis
From: https://www.cnblogs.com/kk4458/p/16998300.html

相关文章

  • python中使用马尔可夫决策过程(MDP)动态编程来解决最短路径强化学习问题|附代码数据
    原文链接:http://tecdat.cn/?p=11105最近我们被客户要求撰写关于MDP的研究报告,包括一些图形和统计输出。在强化学习中,我们有兴趣确定一种最大化获取奖励的策略。假设环境......
  • 力扣-581-最短无序连续子序列
    能不能把问题转化为找第一个逆序对和最后一个逆序对 intfindUnsortedSubarray(vector<int>&nums){ intres=0; intstartIndex=-1,endIndex=-1; for(inti=......
  • déce. 20 最短网络
    https://www.luogu.com.cn/problem/P1546一遍过#include<bits/stdc++.h>usingnamespacestd;#defineinRead()typedeflonglongll;intin{inti=0,f=1;ch......
  • [ARC044B] 最短路問題
    [ARC044B]最短路問題难度:\(1744\)标签:最短路,记数\(\mathtt{blog}\)有一个\(n\)个点的无向图,\(1\)点为起点,现在告诉你\(1\simn\)点到\(1\)点的最短距离,每条边......
  • dijkstra最短路代码模板更新
     fromcollectionsimportdefaultdictfromheapqimportheappush,heappopdefdijkstra(edges,start_node,end_node):graph=defaultdict(dict)f......
  • e^x 与 ln x 的 最短距离 是 多少 ?
    下午 7点左右,  在知乎看到一题 :   e^x与 lnx 的最短距离是多少? 在消息通知里看到,  没有看到解题过程,  看到这题是高考难度, ......
  • [Code+#4]最短路
    [\(Code\)+#4]最短路链接:https://www.luogu.com.cn/problem/P4366题面:给定一个\(n\)个点,\(m\)条边的无向图,若任意点对\((i,j)\)之间还有一条长为\((ixorj)\timesC\)......
  • [Code+#4]最短路
    [$Code$+#4]最短路链接:https://www.luogu.com.cn/problem/P4366题面:给定一个$n$个点,$m$条边的无向图,若任意点对$(i,j)$之间还有一条长为$(ixorj)\timesC$的边,求$A......
  • PWN ORW 最短的shellcode(33字节!)
    前言:下面的rdx就是read(1,buf,n)中的n,这个值太大或者太小都没办法正常读。所以分两种大情况:orw:(64bit,34字节,针对需要调整rdx的情况:)shellcode=asm('''movedx,0x6761......
  • P5905 【模板】Johnson 全源最短路
    P5905【模板】Johnson全源最短路...处理负权边的方法十分巧妙,就像是势能一样算法上文链接有详解,就不赘述了,这样就实现了dij也可以处理负边是需要提前预处理一遍,建立......