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

用迪杰斯特拉算法实现有向网的最短路径
输入格式:
第一行输入有向网的顶点和边数,第二行输入各顶点值,用空格间隔,第三行开始输入各条边的 两个点的及边上的权值,用空格间隔。最后一行输入要求路径的两个顶点。
输出格式:
输出最短路径经过的各顶点,中间用–>连接。

include

include

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

include

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;

}