In five-axis machining, it is significant to design tool orientations with better performance at each given CC point. Plakhotnik and Lauwers (2014) presented a graph-based method to optimize tool orientation. They transformed the optimization problem to the shortest path problem and applied Dijkstra's algorithm to work it out. In this paper, aiming to minimize and smooth the tool orientation changes, a multi-objective problem is built: \begin{equation}\label{multiob} \begin{aligned} \min\ &\underset{i}{\max} \left| \omega_i \right|\\ \min\ &\underset{i}{\max} \left| a_i \right|\\ s.t.\ &\left| \omega_i \right|\leqslant\ \Omega_{max},\ & i\in \{1,\cdots,N\}, \end{aligned} \end{equation} where $\omega_i$ and $a_i$ represent the quasi-velocity and quasi-acceleration of tool orientation respectively, $N$ is the number of CC points on a tool path, and $\Omega_{max}$ is the maximal velocity of the rotation axes. However, the two objects cannot be optimized at the same time. So we use the summation of two exponential functions to approximate the objective function. The multi-objective problem is transformed to a single objective problem: \begin{equation}\label{singleob} \begin{aligned} \min\,\, &\sum\limits_{i=1}^N (s^{\vert a_i \vert}+t^{\vert \omega_i \vert})\\ s.t.\ &\left| \omega_i \right|\leqslant\ \Omega_{max},\ & i\in \{1,\cdots,N\}, \end{aligned} \end{equation} where $s$ and $t$ are to be determined. Aiming to solve the above optimization problem, we introduce a new concept namely {\em difference graph}. Given a hierarchical weighted directed graph $G$, its difference graph $G'$ can be constructed. Furthermore, the weight of each edge in $G'$ is set such that the shortest path has the "smooth" property. Applying Dijkstra's algorithm and a refine algorithm, we can obtain the optimized tool orientations at each CC points. Compared with Plakhotnik and Lauwers's method, our method can obtain a smoother tool orientations, while the whole changes of tool orientations are close in both methods.