最短路径问题的Dijkstra算法 

是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树>    。该算法常用于路由算法或者作为其他图算法的一个子模块。 

# Dijkstra's algorithm for shortest paths
# David Eppstein, UC Irvine, 4 April 2002

# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
from priodict import priorityDictionary

def Dijkstra(G,start,end=None):
	"""
	Find shortest paths from the  start vertex to all vertices nearer than or equal to the end.

	The input graph G is assumed to have the following representation:
	A vertex can be any object that can be used as an index into a dictionary.
	G is a dictionary, indexed by vertices.  For any vertex v, G[v] is itself a dictionary,
	indexed by the neighbors of v.  For any edge v->w, G[v][w] is the length of the edge.
	This is related to the representation in <http://www.python.org/doc/essays/graphs.html>
	where Guido van Rossum suggests representing graphs as dictionaries mapping vertices
	to lists of outgoing edges, however dictionaries of edges have many advantages over lists:
	they can store extra information (here, the lengths), they support fast existence tests,
	and they allow easy modification of the graph structure by edge insertion and removal.
	Such modifications are not needed here but are important in many other graph algorithms.
	Since dictionaries obey iterator protocol, a graph represented as described here could
	be handed without modification to an algorithm expecting Guido's graph representation.

	Of course, G and G[v] need not be actual Python dict objects, they can be any other
	type of object that obeys dict protocol, for instance one could use a wrapper in which vertices
	are URLs of web pages and a call to G[v] loads the web page and finds its outgoing links.
	
	The output is a pair (D,P) where D[v] is the distance from start to v and P[v] is the
	predecessor of v along the shortest path from s to v.
	
	Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive.
	This code does not verify this property for all edges (only the edges examined until the end
	vertex is reached), but will correctly compute shortest paths even for some graphs with negative
	edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.
	"""

	D = {}	# dictionary of final distances
	P = {}	# dictionary of predecessors
	Q = priorityDictionary()	# estimated distances of non-final vertices
	Q[start] = 0
	
	for v in Q:
		D[v] = Q[v]
		if v == end: break
		
		for w in G[v]:
			vwLength = D[v] + G[v][w]
			if w in D:
				if vwLength < D[w]:
					raise ValueError, "Dijkstra: found better path to already-final vertex"
			elif w not in Q or vwLength < Q[w]:
				Q[w] = vwLength
				P[w] = v
	
	return (D,P)
			
def shortestPath(G,start,end):
	"""
	Find a single shortest path from the given start vertex to the given end vertex.
	The input has the same conventions as Dijkstra().
	The output is a list of the vertices in order along the shortest path.
	"""

	D,P = Dijkstra(G,start,end)
	Path = []
	while 1:
		Path.append(end)
		if end == start: break
		end = P[end]
	Path.reverse()
	return Path

# example, CLR p.528
G = {'s': {'u':10, 'x':5},
	'u': {'v':1, 'x':2},
	'v': {'y':4},
	'x':{'u':3,'v':9,'y':2},
	'y':{'s':7,'v':6}}

print Dijkstra(G,'s')
print shortestPath(G,'s','v')

阅读全文……

发表评论

IT瘾于2014年6月22日 上午01时16分00秒发布 #

广州基础养老金、个人账户养老金、过渡性养老金、过渡性调节金分别按下列办法计算：

　　定义：以当地上年度在岗职工月平均工资和本人指数化月平均缴费工资的平均值为基数，缴费每满1年发给1%。

　　计算公式为：基础养老金=(参保人员退休时当地上年度在岗职工月平均工资+本人指数化月平均缴费工资)÷2×缴费年限×1%

　　其中：指数化月平均缴费工资=当地上年度在岗职工月平均工×本人平均缴费指数

　　个人的平均缴费指数：

阅读全文……

发表评论

IT瘾于2014年6月22日 上午12时58分00秒发布 #

Chart interactivity

If you are looking to add interaction as a layer to charts, Chart.js is not the library for you. A better option would be using SVG, as this will let you attach event listeners to any of the elements in the chart, as these are all DOM nodes.

Chart.js uses the canvas element, which is a single DOM node, similar in characteristics to a static image. This does mean that it has a wider scope for compatibility, and less memory implications than SVG based charting solutions. The canvas element also allows for saving the contents as a base 64 string, allowing saving the chart as an image.

In SVG, all of the lines, data points and everything you see is a DOM node. As a result of this, complex charts with a lot of intricacies, or many charts on the page will often see dips in performance when scrolling or generating the chart, especially when there are multiple on the page. SVG also has relatively poor mobile support, with Android not supporting SVG at all before version 3.0, and iOS before 5.0. (caniuse.com/svg-html5).

Browser support

Browser support for the canvas element is available in all modern & major mobile browsers (caniuse.com/canvas).

For IE8 & below, I would recommend using the polyfill ExplorerCanvas - available at https://code.google.com/p/explorercanvas/. It falls back to Internet explorer's format VML when canvas support is not available. Example use:

<head> 	<!--[if lte IE 8]> 		<script src="excanvas.js"></script> 	<![endif]--> </head>

Usually I would recommend feature detection to choose whether or not to load a polyfill, rather than IE conditional comments, however in this case, VML is a Microsoft proprietary format, so it will only work in IE.

Some important points to note in my experience using ExplorerCanvas as a fallback.

• Initialise charts on load rather than DOMContentReady when using the library, as sometimes a race condition will occur, and it will result in an error when trying to get the 2d context of a canvas.
• New VML DOM elements are being created for each animation frame and there is no hardware acceleration. As a result animation is usually slow and jerky, with flashing text. It is a good idea to dynamically turn off animation based on canvas support. I recommend using the excellentModernizr to do this.
• When declaring fonts, the library explorercanvas requires the font name to be in single quotes inside the string. For example, instead of your scaleFontFamily property being simply "Arial", explorercanvas support, use "'Arial'" instead. Chart.js does this for default values.
•  

阅读全文……

发表评论

IT瘾于2014年6月16日 下午10时58分00秒发布 #