类包括根据顶点数和边初始化的构造函数，添加边，求两点最短路径等函数
1. 邻接矩阵
class Graph {
private:
vector<vector<int>> graph;
public:
Graph(int n, vector<vector<int>>& edges) {
graph.resize(n,vector<int>(n,INT_MAX/2));
for(auto&edge:edges){
int from = edge[0];
int to = edge[1];
graph[from][to] = edge[2];
}
}
void addEdge(vector<int> edge) {
int from = edge[0];
int to = edge[1];
graph[from][to] = edge[2];
}
int shortestPath(int node1, int node2) {
int n = graph.size();
vector<bool> vis(n);
vector<int> dis(n,INT_MAX/2);
dis[node1] = 0;
for(int times=0;times<n;times++){//最多遍历n次
int cur = -1;
for(int i=0;i<n;i++){//贪心找最小值
if(vis[i]||dis[i]==INT_MAX/2) continue;//跳过已经选取的点和无法到达的点
if(cur==-1||dis[i]<dis[cur]) cur = i;
}
if(cur==-1) return -1;//表示无法到达目标
if(cur==node2) break; //找到目标直接跳出，此时dis[cur]即为最短路径，无需再更新
vis[cur] = 1;
//找到当前最近点后，根据最近点进行更新
for(int i=0;i<n;i++){
if(vis[i]||graph[cur][i]==INT_MAX/2) continue;//对应点已选取，或对应的边不存在，无需更新
dis[i] = min(dis[i],dis[cur]+graph[cur][i]);
}
}
return dis[node2]==INT_MAX/2?-1:dis[node2];
}
};