Dijkstra的双栈算术表达式求值算法

Dijkstra的双栈算术表达式求值算法。C++实现Dijkstra算法

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int INF = INT_MAX;

struct Node{
 int pre;
 int dist;
 bool visited;
 Node() : pre(-1), dist(INF), visited(false) {}
};


void dispT(vector & T) {
 for (int i = 0; i < T.size(); ++i) {
  cout << "Num: " << i << "  Dist: " 
   << T[i].dist << "  Pre: " << T[i].pre << endl;
 }
 return;
}

int Extract_Min(vector & T) {
 int mark = -1;
 for (int i = 0; i < T.size(); ++i) {
  if (!T[i].visited) {
   if (mark == -1)
    mark = i;
   else if (T[i].dist < T[mark].dist)
    mark = i;
  }
 }
 return mark;
}

void Dijkstra(vector > & G, size_t src)
{
 //check validity.
 if (src >= G.size()) 
  return;

 vector T(G.size());
 T[src].dist = 0;

 for (int i = 0; i < G.size(); ++i) {
  int tag = Extract_Min(T);
  assert(tag != -1); //debug.

  T[tag].visited = true;
  //update the weights of edges,taversing in the same manner as BFS.
  for (int j = 0; j < G.size(); ++j) {
   if (!T[j].visited && G[tag][j] != INF 
    && T[j].dist > G[tag][j] + T[tag].dist) {
    T[j].dist = G[tag][j] + T[tag].dist;
    T[j].pre = tag;
   }
  }
 }

 //output.
 dispT(T);
}

int main(void)
{
 cout << "Dijkstra Algorithm for Directed Graph:" << endl;

 while (true) {
  int N;
  cout << "Number of Nodes: ";
  cin >> N;
  vector >
   G(N, vector(N, INF));
  for (int i = 0; i < N; ++i)
   G[i][i] = 0;

  int M;
  cout << "Number of Edges: ";
  cin >> M;
  for (int i = 0; i < M; ++i) {
   int s, e;
   cin >> s >> e;
   cin >> G[s][e];
  }

  for (int src = 0; src < N; ++src) {
   cout << "From " << src << " :" << endl;
   Dijkstra(G, src);
   system("pause");
  }
 }
 system("pause");
 return 0;
}

#define
_CRT_SECURE_NO_WARNINGS#include #include #include #include
#include #include #include#include #include #include using
namespace std;const int INF =…

后生可畏、原作链接

http://blog.csdn.net/u011638883/article/details/17200869
原作是关于Dijkstra算法的解说与落实。依然老话x 如有侵害权益,立时删除。

图片 1图片 2

二、算法精晓

以下是自己根据个人掌握扯的。
最短路线算法的贯彻实际上是将图上全数一点点分为三个集聚,一个是未加入的点的集合A,一个是已插手的点的集合B。大器晚成发轫独有起源S在集合中,每一遍遍历全数一些都会选出路线最短的点步向集合B中,并更新最短路线。
当集合B中找到指标点也许集结A中未有一些时,将跳出循环。

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 template<typename T>
 6 class Stack
 7 {
 8 private:
 9     T stack[100];
10     int i = 0;
11 public:
12     Stack() = default;
13 
14     T pop()
15     {
16         if (i == -1)
17         {
18             cout << "栈已空!" << endl;
19             return 0;
20         }
21 
22         T top = stack[i - 1];
23         --i;
24         return top;
25     }
26 
27     void push(T num)
28     {
29         ++i;
30         stack[i - 1] = num;
31     }
32 
33     void clear()
34     {
35         for (int j = 0; j < 100; ++j)
36         {
37             T[j] = 0;
38         }
39     }
40 };
41 
42 int main()
43 {
44     Stack<string> ops;
45     Stack<double> num;
46     string str;
47 
48     std::cout << "请输入计算式: " << endl;
49     cout << "注: 每个字符间请以空格分开,子表达式请用括号括起注明" << endl;
50     cout << "字符 E 代表结束" << endl;
51     while (true)
52     {
53         cin >> str;
54              if (str == "(")      continue;
55         else if (str == "+") ops.push(str);
56         else if (str == "-") ops.push(str);
57         else if (str == "*") ops.push(str);
58         else if (str == "/") ops.push(str);
59         else if (str == ")")
60         {
61             string op = ops.pop();
62             double val = num.pop();
63             if (op == "+") val = num.pop() + val;
64             if (op == "-") val = num.pop() - val;
65             if (op == "*") val = num.pop() * val;
66             if (op == "/") val = num.pop() / val;
67             num.push(val);
68         }
69 
70         else if (str != "E")
71         {
72             double val = stod(str);
73             num.push(val);
74         }
75              
76         if (str == "E")
77         {
78             break;
79         }
80     }
81 
82     cout << "结果为: ";
83     cout << num.pop() << endl;
84 
85     return 0;
86 }

相关文章