このプログラムの目的は、時刻表の乗り換え案内のアルゴリズムを実現する為のテストプログラムです。
「到着時刻より早い時間の電車やバスには乗れない」をダイクストラに組み込むことができるかを調べたものです。
ノードのValueが到着・出発時間を表わすと考えて下さい。
package main
import (
"fmt"
"math"
)
type Node struct {
Name string
Value float64
}
type Edge struct {
From *Node
To *Node
Weight float64
}
func main() {
nodeA := &Node{Name: "A", Value: 1}
nodeB := &Node{Name: "B", Value: 1}
nodeC := &Node{Name: "C", Value: 0}
nodeD := &Node{Name: "D", Value: 1}
nodeE := &Node{Name: "E", Value: 1}
edges := []Edge{
{nodeA, nodeB, 1},
{nodeA, nodeC, 1},
{nodeB, nodeC, 1},
{nodeB, nodeD, 1},
{nodeC, nodeD, 1},
{nodeC, nodeE, 1},
{nodeE, nodeD, 1},
{nodeD, nodeE, 1},
}
startNode := nodeA
targetNode := nodeE
shortestPath, totalWeight := dijkstra(startNode, targetNode, edges)
if shortestPath == nil {
fmt.Println("最短経路が見つかりませんでした。")
} else {
fmt.Printf("最短経路: %v\n", getNodeNames(shortestPath))
fmt.Printf("最短経路の総重み: %.2f\n", totalWeight)
}
}
func dijkstra(startNode, targetNode *Node, edges []Edge) ([]*Node, float64) {
shortestDistances := make(map[*Node]float64)
predecessors := make(map[*Node]*Node)
for _, edge := range edges {
shortestDistances[edge.From] = math.Inf(1)
shortestDistances[edge.To] = math.Inf(1)
}
shortestDistances[startNode] = 0
visitedNodes := make(map[*Node]bool)
for len(visitedNodes) < len(shortestDistances) {
currentNode := getClosestUnvisitedNode(shortestDistances, visitedNodes)
if currentNode == nil || currentNode == targetNode {
break
}
for _, edge := range edges {
if edge.From == currentNode && edge.To.Value >= currentNode.Value {
distance := shortestDistances[currentNode] + edge.Weight
if distance < shortestDistances[edge.To] {
shortestDistances[edge.To] = distance
predecessors[edge.To] = currentNode
}
}
}
visitedNodes[currentNode] = true
}
shortestPath := make([]*Node, 0)
currentNode := targetNode
for currentNode != nil {
shortestPath = append([]*Node{currentNode}, shortestPath...)
currentNode = predecessors[currentNode]
}
totalWeight := shortestDistances[targetNode]
return shortestPath, totalWeight
}
func getClosestUnvisitedNode(distances map[*Node]float64, visitedNodes map[*Node]bool) *Node {
minDistance := math.Inf(1)
var closestNode *Node
for node, distance := range distances {
if !visitedNodes[node] && distance < minDistance {
minDistance = distance
closestNode = node
}
}
return closestNode
}
func getNodeNames(nodes []*Node) []string {
names := make([]string, len(nodes))
for i, node := range nodes {
names[i] = node.Name
}
return names
}