/***********************************************************
dijkstra.c -- 最短路問題
使用例: dijkstra <dijkstra.dat
***********************************************************/
#console
Declare Function printf CDECL Lib"msvcrt" (fmt As *Byte, ...) As Long
Declare Function scanf CDECL Lib"msvcrt" (fmt As *Byte, ...) As Long
Const INT_MAX = 2147483647
Const NMAX = 100 /* 点の数の上限 */
Dim weight[NMAX, NMAX] As Long /* 辺の重み */
Dim n As Long /* 点の数 */
Sub readweight() /* データ入力 */
Dim i As Long, j As Long, x As Long
If (scanf(Ex"%d%*[^\n]", VarPtr(n)) <> 1 Or n > NMAX) Then
n = 0
Exit Sub
End If
For i = 1 To n
For j = 1 To n
weight[i, j] = INT_MAX
Next
Next
While (scanf(Ex"%d%d%d%*[^\n]", VarPtr(i), VarPtr(j), VarPtr(x)) = 3)
weight[i, j] = x
weight[j, i] = x
Wend
printf(Ex"データ weight(i,j)\n")
For i = 1 To n
For j = 1 To n
If (weight[i, j] < INT_MAX) Then
printf(Ex"%3d", weight[i, j])
Else
printf(Ex" ∞")
End If
Next
printf(Ex"\n")
Next
End Sub
Const START = 1 /* 出発点 */
Function main() As Long
Dim i As Long, j As Long, inext As Long, min As Long
Dim visited[NMAX] As Byte
Dim distance[NMAX] As Long, prev[NMAX] As Long
readweight() /* 点の数n, 距離weight[1..n, 1..n]を読む */
For i = 1 To n
visited[i] = FALSE
distance[i] = INT_MAX
Next
distance[START] = 0
inext = START
Do
i = inext
visited[i] = TRUE
min = INT_MAX
For j = 1 To n
If (visited[j]) Then *FOR_CONTINUE
If (weight[i, j] < INT_MAX And distance[i] + weight[i, j] < distance[j]) Then
distance[j] = distance[i] + weight[i, j]
prev[j] = i
End If
If (distance[j] < min) Then
min = distance[j]: inext = j
End If
*FOR_CONTINUE
Next
Loop while (min < INT_MAX)
printf(Ex"点 直前の点 最短距離\n")
For i = 1 To n
If (i <> START And visited[i]) Then
printf(Ex"%2d%10d%10d\n", i, prev[i], distance[i])
End If
Next
main = 0
End Function
main()
