dijkstra算法实现C++

//#include<iostream> //#include<vector> //#include<stack> //using namespace std; // //#define maxv 100 //int eTop = 0; //vector<int> st; //stack<int> stk; //#define INF 100001 //int src[maxv][maxv]; // //class Data //{ //public: // Data(int u, int v, int len) // { // this->m_u = u; // this->m_v = v; // this->m_len = len; // } // int m_u; // int m_v; // int m_len; //}; // //void insertData(vector<Data>& vd) //{ // Data d1(1, 2, 4); // Data d2(1, 3, 6); // Data d3(1, 4, 6); // Data d4(2, 3, 1); // Data d5(2, 5, 7); // Data d6(3, 5, 6); // Data d7(3, 6, 4); // Data d8(4, 3, 2); // Data d9(4, 6, 5); // Data d10(5, 7, 6); // Data d11(6, 5, 1); // Data d12(6, 7, 8); // vd.push_back(d1); // vd.push_back(d2); // vd.push_back(d3); // vd.push_back(d4); // vd.push_back(d5); // vd.push_back(d6); // vd.push_back(d7); // vd.push_back(d8); // vd.push_back(d9); // vd.push_back(d10); // vd.push_back(d11); // vd.push_back(d12); //} // ////边的结构体 //struct Edge //{ // int u, v, len; // Edge* next; //}epool[maxv]; // ////点的结构体 //struct Node //{ // Edge* first; //}; // //struct Graph //{ // int e, n; // Node adj[maxv]; //}; // //bool dfs(Graph& g, int u) //{ // st[u] = 1; // while (g.adj[u].first) // { // int v = g.adj[u].first->v; // if (st[v] == 1) // { // return true; // } // if (!st[v] && dfs(g, v)) // { // return true; // } // g.adj[u].first = g.adj[u].first->next; // } // st[u] = -1; // stk.push(u); // return false; //} // //void addEdge(Graph& g, int u, int v, int len) //{ // epool[eTop].u = u; // epool[eTop].v = v; // epool[eTop].len = len; // epool[eTop].next = g.adj[u].first; // g.adj[u].first = &epool[eTop]; // eTop++; //} // //void creatGraph(Graph& g) //{ // vector<Data> vd; // insertData(vd); // g.n = 7; // st.assign(g.n + 1, 0); //将st数组内的值初始化为0 // for (int i = 0; i <= g.n; i++) // { // g.adj[i].first = NULL; // } // g.e = vd.size(); // for (auto it = vd.begin(); it != vd.end(); it++) // { // addEdge(g, (*it).m_u, (*it).m_v, (*it).m_len); // addEdge(g, (*it).m_v, (*it).m_u, (*it).m_len); // } // Graph g1 = g; // for (int i = 1; i <= g.n; i++) // { // if (!st[i] && dfs(g1, i)) // { // cout << "图中有环！" << endl; // } // } //} // //int minDis(Graph g, int* dis) //{ // int min = 0; // int minId = 1; // while (minId <= g.n) // { // if (st[minId] == 0) // { // min = minId; // break; // } // minId++; // } // int i = 1; // while (i <= g.n) // { // while (st[i]) // { // i++; // } // if (dis[min] > dis[i]) // { // min = i; // } // i++; // } // return min; //} // //void dijkstra(Graph g, int start, int src[maxv][maxv]) //{ // int dis[maxv]; // st.assign(g.n + 1, 0); // for (int i = 1; i <= g.n; i++) // { // if (i == start) // { // dis[i] = 0; // } // else // { // dis[i] = INF; // } // } // int end = 1; // int next = 0; // for (int i = 1; i <= g.n; i++) // { // end = end * st[i]; // } // while (!end) // { // next = minDis(g, dis); // Graph g1 = g; // while (g1.adj[next].first) // { // if (dis[g1.adj[next].first->v] > dis[next] + src[next][g1.adj[next].first->v]) // { // dis[g1.adj[next].first->v] = dis[next] + src[next][g1.adj[next].first->v]; // } // g1.adj[next].first = g1.adj[next].first->next; // } // st[next] = 1; // end = 1; // for (int i = 1; i <= g.n; i++) // { // end = end * st[i]; // } // for (int j = 1; j <= g.n; j++) // { // cout << dis[j] << " "; // } // cout << endl; // } // for (int i = 1; i <= g.n; i++) // { // if (i != start) // { // cout << "从" << start << "到" << i << "的最短路径为：" << " "; // cout << dis[i] << " "; // } // cout << endl; // } //} // //void initArray(Graph g, int src[maxv][maxv]) //{ // for (int i = 1; i <= g.n; i++) // { // for (int j = 1; j <= g.n; j++) // { // if (i == j) // { // src[i][j] = 0; // } // else // { // src[i][j] = INF; // } // } // } // for (int i = 1; i <= g.n; i++) // { // while (g.adj[i].first) // { // src[i][g.adj[i].first->v] = g.adj[i].first->len; // g.adj[i].first = g.adj[i].first->next; // } // } // for (int i = 1; i <= g.n; i++) // { // for (int j = 1; j <= g.n; j++) // { // cout << "\t" <<src[i][j] << " "; // } // cout << endl; // } //} // //int main() //{ // Graph g; // creatGraph(g); // while (!stk.empty()) // { // cout << stk.top() << " "; // stk.pop(); // } // cout << endl; // cout << "-----------------------" << endl; // initArray(g, src); // int start; // cout << "请输入起始点：" << endl; // cin >> start; // dijkstra(g, start, src); // system("pause"); // return 0; //}