数据结构-迪杰斯特拉最短路径算法 （C++代码）

解题思路:

    把里面的结点信息变为vector来表示
注意事项:

    vector是一个容器可以用来存放任何类型（包括自定义数据）的数据

参考代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 10e8;
struct Edge{
    int to;
    int dis;
    bool friend operator < (Edge x, Edge y){
        return x.dis > y.dis;
    }
}temp, now;

int tag[55];        //标记数组
int dist[55];       //距离数组 计算距离
vector <Edge> vec[55];//类似于链表保存各个结点的信息
int n;

void init(){
    for(int i = 1; i <= n; i++){
        dist[i] = maxn;
    }
    memset(tag, 0, sizeof(tag));
}

void dij(int f){
    priority_queue <Edge> q;
    init();
    temp.to = f;
    temp.dis = 0;
    q.push(temp);
    dist[f] = 0;
    while(!q.empty()){
        now = q.top();
        q.pop();
        if(!tag[now.to]){
            tag[now.to] = 1;
            for(int i = 0; i < vec[now.to].size(); i++){
                if(!tag[vec[now.to][i].to] && dist[now.to] + vec[now.to][i].dis < dist[vec[now.to][i].to]){
                    dist[vec[now.to][i].to] =  dist[now.to] + vec[now.to][i].dis;
                    temp.to = vec[now.to][i].to;
                    temp.dis = dist[vec[now.to][i].to];
                    q.push(temp);
                }
            }
        }
    }
}

int main(){
    int f;
    int tmp;
    scanf("%d %d", &n, &f);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &tmp);
            if(tmp != 0){
                temp.to = j;
                temp.dis = tmp;
                vec[i].push_back(temp);
            }
        }
    }
    dij(f+1);
    for(int i = 1; i <= n; i++){
        if(i != f+1){
            if(dist[i] == maxn){
                printf("-1 ");
            }else{
                printf("%d ", dist[i]);
            }
        }
    }
    return 0;
}