# Older blog entries for sness (starting at number 5011)

Optimal substructure - Wikipedia, the free encyclopedia

Optimal substructure - Wikipedia, the free encyclopedia: "In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.[1]"

'via Blog this'

Syndicated 2013-01-27 08:48:00 from sness

Dynamic programming - Wikipedia, the free encyclopedia

Dynamic programming - Wikipedia, the free encyclopedia: "Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its subproblems. Consequently, the first step towards devising a dynamic programming solution is to check whether the problem exhibits such optimal substructure. Such optimal substructures are usually described by means of recursion. For example, given a graph G=(V,E), the shortest path p from a vertex u to a vertex v exhibits optimal substructure: take any intermediate vertex w on this shortest path p. If p is truly the shortest path, then the path p1 from u to w and p2 from w to v are indeed the shortest paths between the corresponding vertices (by the simple cut-and-paste argument described in Introduction to Algorithms). Hence, one can easily formulate the solution for finding shortest paths in a recursive manner, which is what the Bellman-Ford algorithm or the Floyd-Warshall algorithm does.
"

'via Blog this'

Syndicated 2013-01-27 08:48:00 from sness

Python - Dijkstra's Algorithm - Stack Overflow

Python - Dijkstra's Algorithm - Stack Overflow: "
0
down vote
accepted
As mentioned above, you can use an instance of an object.

This author has a pretty convincing python implementation of Dijkstras in python.

"

'via Blog this'

Syndicated 2013-01-27 01:21:00 from sness

Dijkstra's algorithm - Wikipedia, the free encyclopedia

Dijkstra's algorithm - Wikipedia, the free encyclopedia: "For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as "visited" at this time, and it remains in the unvisited set."

'via Blog this'

Syndicated 2013-01-27 01:21:00 from sness

Dijkstra's algorithm for shortest paths « Python recipes « ActiveState Code

Dijkstra's algorithm for shortest paths « Python recipes « ActiveState Code: "

6

Dijkstra(G,s) finds all shortest paths from s to each other vertex in the graph, and shortestPath(G,s,t) uses Dijkstra to find the shortest path from s to t. Uses the priorityDictionary data structure (Recipe 117228) to keep track of estimated distances to each vertex.

Python, 87 lines"

'via Blog this'

Syndicated 2013-01-27 01:20:00 from sness

Lecture 10 - Dynamic Programming - YouTube

Lecture 10 - Dynamic Programming - YouTube: "