2 https://www.cnblogs.com/NEWzyz/p/8920706.html
示例代码
python
# the graph graph = {} graph["start"] = {} graph["start"]["a"] = 6 graph["start"]["b"] = 2 graph["a"] = {} graph["a"]["fin"] = 1 graph["b"] = {} graph["b"]["a"] = 3 graph["b"]["fin"] = 5 graph["fin"] = {} # the costs table infinity = float("inf") costs = {} costs["a"] = 6 costs["b"] = 2 costs["fin"] = infinity # the parents table parents = {} parents["a"] = "start" parents["b"] = "start" parents["fin"] = None processed = [] def find_lowest_cost_node(costs): lowest_cost = float("inf") lowest_cost_node = None # Go through each node. for node in costs: cost = costs[node] # If it's the lowest cost so far and hasn't been processed yet... if cost < lowest_cost and node not in processed: # ... set it as the new lowest-cost node. lowest_cost = cost lowest_cost_node = node return lowest_cost_node # Find the lowest-cost node that you haven't processed yet. node = find_lowest_cost_node(costs) # If you've processed all the nodes, this while loop is done. while node is not None: cost = costs[node] # Go through all the neighbors of this node. neighbors = graph[node] for n in neighbors.keys(): new_cost = cost + neighbors[n] # If it's cheaper to get to this neighbor by going through this node... if costs[n] > new_cost: # ... update the cost for this node. costs[n] = new_cost # This node becomes the new parent for this neighbor. parents[n] = node # Mark the node as processed. processed.append(node) # Find the next node to process, and loop. node = find_lowest_cost_node(costs) print("Cost from the start to each node:") print(costs) print(graph)C#
using System; using System.Collections.Generic; namespace ConsoleApplication { public class Program { private const double _infinity = double.PositiveInfinity; private static Dictionary<string, Dictionary<string, double>> _graph = new Dictionary<string, Dictionary<string, double>>(); private static List<string> _processed = new List<string>(); public static void Main(string[] args) { _graph.Add("start", new Dictionary<string, double>()); _graph["start"].Add("a", 6.0); _graph["start"].Add("b", 2.0); _graph.Add("a", new Dictionary<string, double>()); _graph["a"].Add("fin", 1.0); _graph.Add("b", new Dictionary<string, double>()); _graph["b"].Add("a", 3.0); _graph["b"].Add("fin", 5.0); _graph.Add("fin", new Dictionary<string, double>()); var costs = new Dictionary<string, double>(); costs.Add("a", 6.0); costs.Add("b", 2.0); costs.Add("fin", _infinity); var parents = new Dictionary<string, string>(); parents.Add("a", "start"); parents.Add("b", "start"); parents.Add("fin", null); var node = FindLowestCostNode(costs); while (node != null) { var cost = costs[node]; var neighbors = _graph[node]; foreach (var n in neighbors.Keys) { var new_cost = cost + neighbors[n]; if (costs[n] > new_cost) { costs[n] = new_cost; parents[n] = node; } } _processed.Add(node); node = FindLowestCostNode(costs); } Console.WriteLine(string.Join(", ", costs)); } private static string FindLowestCostNode(Dictionary<string, double> costs) { var lowestCost = double.PositiveInfinity; string lowestCostNode = null; foreach (var node in costs) { var cost = node.Value; if (cost < lowestCost && !_processed.Contains(node.Key)) { lowestCost = cost; lowestCostNode = node.Key; } } return lowestCostNode; } } }Java
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class DijkstrasAlgorithm { // the graph private static Map<String, Map<String, Double>> graph = new HashMap<>(); private static List<String> processed = new ArrayList<>(); private static String findLowestCostNode(Map<String, Double> costs) { Double lowestCost = Double.POSITIVE_INFINITY; String lowestCostNode = null; // Go through each node for (Map.Entry<String, Double> node : costs.entrySet()) { Double cost = node.getValue(); // If it's the lowest cost so far and hasn't been processed yet... if (cost < lowestCost && !processed.contains(node.getKey())) { // ... set it as the new lowest-cost node. lowestCost = cost; lowestCostNode = node.getKey(); } } return lowestCostNode; } public static void main(String[] args) { graph.put("start", new HashMap<>()); graph.get("start").put("a", 6.0); graph.get("start").put("b", 2.0); graph.put("a", new HashMap<>()); graph.get("a").put("fin", 1.0); graph.put("b", new HashMap<>()); graph.get("b").put("a", 3.0); graph.get("b").put("fin", 5.0); graph.put("fin", new HashMap<>()); // The costs table Map<String, Double> costs = new HashMap<>(); costs.put("a", 6.0); costs.put("b", 2.0); costs.put("fin", Double.POSITIVE_INFINITY); // the parents table Map<String, String> parents = new HashMap<>(); parents.put("a", "start"); parents.put("b", "start"); parents.put("fin", null); String node = findLowestCostNode(costs); while (node != null) { Double cost = costs.get(node); // Go through all the neighbors of this node Map<String, Double> neighbors = graph.get(node); for (String n : neighbors.keySet()) { double newCost = cost + neighbors.get(n); // If it's cheaper to get to this neighbor by going through this node if (costs.get(n) > newCost) { // ... update the cost for this node costs.put(n, newCost); // This node becomes the new parent for this neighbor. parents.put(n, node); } } // Mark the node as processed processed.add(node); // Find the next node to process, and loop node = findLowestCostNode(costs); } System.out.println("Cost from the start to each node:"); System.out.println(costs); // { a: 5, b: 2, fin: 6 } } }
JS
'use strict'; // the graph const graph = {}; graph["start"] = {}; graph["start"]["a"] = 6; graph["start"]["b"] = 2; graph["a"] = {}; graph["a"]["fin"] = 1; graph["b"] = {}; graph["b"]["a"] = 3; graph["b"]["fin"] = 5; graph["fin"] = {}; // The costs table const costs = {}; costs['a'] = 6; costs['b'] = 2; costs['fin'] = Infinity; // the parents table const parents = {}; parents['a'] = 'start'; parents['b'] = 'start'; parents['fin'] = null; let processed = []; function find_lowest_cost_node(costs) { let lowest_cost = Infinity; let lowest_cost_node = null; // Go through each node for (let node in costs) { let cost = costs[node]; // If it's the lowest cost so far and hasn't been processed yet... if (cost < lowest_cost && (processed.indexOf(node) === -1)) { // ... set it as the new lowest-cost node. lowest_cost = cost; lowest_cost_node = node; } } return lowest_cost_node; } let node = find_lowest_cost_node(costs); while (node !== null) { let cost = costs[node]; // Go through all the neighbors of this node let neighbors = graph[node]; Object.keys(neighbors).forEach(function(n) { let new_cost = cost + neighbors[n]; // If it's cheaper to get to this neighbor by going through this node if (costs[n] > new_cost) { // ... update the cost for this node costs[n] = new_cost; // This node becomes the new parent for this neighbor. parents[n] = node; } }); // Mark the node as processed processed = processed.concat(node); // Find the next node to process, and loop node = find_lowest_cost_node(costs); } console.log("Cost from the start to each node:"); console.log(costs); // { a: 5, b: 2, fin: 6 }
