# 7-2 迪杰斯特拉方法实现最短路径(7-2 dijestra method to achieve the shortest path)-其他

## 7-2 迪杰斯特拉方法实现最短路径(7-2 dijestra method to achieve the shortest path)

### include

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;
``````

}

————————

Using dijestra algorithm to realize the shortest path of directed network
Input format:
The first line inputs the number of vertices and edges of the directed net, the second line inputs the values of each vertex, separated by spaces, and the third line starts to input the weights of two points and edges of each edge, separated by spaces. In the last line, enter the two vertices of the desired path.
Output format:
Output the vertices passed by the shortest path, with — & gt; connect.

### include

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;
``````

}